Cod sursa(job #477929)

Utilizator azotlichidAdrian Vladu azotlichid Data 16 august 2010 18:05:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <string>
using namespace std;

#define NMAX 2000005

char needle[NMAX], haystack[NMAX];
int pi[NMAX];
int N, M;

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	gets(needle);
	gets(haystack);
	N = strlen(needle);
	M = strlen(haystack);
//	scanf("%s %s", &needle, &haystack);


	int k = pi[0] = -1;
	for (int i = 1; i < N; i++) {
		while (k > -1 && needle[i] != needle[k+1])
			k = pi[k];
		if (needle[i] == needle[k+1]) ++k;
		pi[i] = k;
	}

	k = -1;
	vector<int> r;

	for (int i = 0; i < M; i++) {
		while (k > -1 && haystack[i] != needle[k+1])
			k = pi[k];
		if (haystack[i] == needle[k+1]) 
			++k;
		if (k+1 == N) {
			r.push_back(i-N+1);
			k = pi[k];
		}
	}
	printf("%d\n", r.size());
	int cnt = 0;
	for (vector<int> :: iterator it = r.begin(); it != r.end() && cnt < 1000; it++, cnt++)
		printf("%d ", *it);
	printf("\n");
	return 0;
}