Cod sursa(job #493754)

Utilizator elmercerAlex Mercer elmercer Data 19 octombrie 2010 14:22:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <string.h>

const long MAX = 2000010;
char A[MAX], B[MAX];
long n,m;
long pi[MAX],i,k;
long nr, Store[1000];

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s\n%s\n", A+1, B+1);

	n = strlen(A + 1);
	m = strlen(B + 1);

	pi[1] = 0; k = 0;
	for (i = 2; i <= n; ++i) {
		while (k > 0 && A[i] != A[k + 1]) {
			k = pi[k];
		}
		if (A[i] == A[k + 1]) {
			++k;
		}
		pi[i] = k;
	}

	k = 0;
	for (i = 1; i <= m; ++i) {
		while (A[k + 1] != B[i] && k > 0) {
			k = pi[k];
		}
		if (A[k + 1] == B[i]) {
			++k;
		}
		if (k == n) {
			++nr;
			if (Store[0] < 1000) {
				Store[++Store[0]] = i - n;
			}
		}
	}
	printf("%ld\n", nr);
	for (i = 1; i <= Store[0]; ++i) {
		printf("%ld ", Store[i]);
	}
	return 0;
}