Cod sursa(job #1700292)

Utilizator mihai995mihai995 mihai995 Data 9 mai 2016 23:14:46
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

const int N = 2 + 2e6;

char text[N], patt[N];
vector<int> sol;
int pi[N];

void kmp(char* text, char* patt){
	pi[0] = -1; pi[1] = 0;
	for (int i = 2, k = 0; patt[i]; i++, k++){
		while ( k >= 0 && patt[k + 1] != patt[i] )
			k = pi[k];
		pi[i] = k + 1;
	}
	for (int i = 1, k = 0; text[i]; i++, k++){
		while ( k >= 0 && patt[k + 1] != text[i] )
			k = pi[k];
		if ( !patt[k + 2] )
			sol.push_back(i - k);
	}
}

int main(){
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	cin >> (patt + 1) >> (text + 1);
	kmp(text, patt);

	cout << sol.size() << '\n';
	for (int i = 0; i < sol.size() && i < 1000; i++)
		cout << sol[i] - 1 << ' ';
	cout << '\n';
	return 0;
}