Cod sursa(job #153912)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 10 martie 2008 20:05:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <cstring>

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

int main() {
	freopen("strmatch.in", "r", stdin);
	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;
		}
	}

	freopen("strmatch.out", "w", stdout);
	printf("%ld\n", nr);
	for (i=1; i<=Store[0]; ++i)
		printf("%ld ", Store[i]);
	return 0;
}