Cod sursa(job #415240)

Utilizator pykhNeagoe Alexandru pykh Data 11 martie 2010 00:29:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<cstdio>
#include<cstring>
const char in[]="strmatch.in", out[]="strmatch.out";
const int N = 2000005;
const int M = 1000;
char a[N], b[N];
int p[N], v[M+5], n, m, k, nr;
int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		scanf("%s %s", a, b);
		n = strlen(a) ;m = strlen(b) ;
		p[0]=p[1]=0;
		k=0;
		int i;
		for(i = 1 ; i < n; ++i)
		{
			while(k > 0 && a[i] != a[k]) k = p[k];
			if(a[i] == a[k]) ++k;
			p[i + 1] = k;
		}
		k = 0;
		for(i = 0; i < m; ++i)
		{
			while(k > 0 && a[k] != b[i])k = p[k];
			if(a[k] == b[i]) ++k;
			if( k == n)
			{
				if( ++nr < M )v[ nr ] = i - n +1 ;
				k = p[ k ];
			}
		}
		printf("%d\n",nr);
		for(int i = 1; i <= (nr < M ? nr : M ); ++i)
			printf("%d ", v[i]);
		return 0;
}