Cod sursa(job #505657)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 3 decembrie 2010 15:12:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<cstdio>
#include<cstring>
void read(),solve();
int i,lenA,lenB,k,q,nr,v[1100],prefix[2000005];
char A[2000005],B[2000005];
int main()
{
	read();
	solve();
}
void read()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	//for(i=1;;i++){scanf("%c",&A[i]);if(A[i]<32)break;}lenA=i-1;
	//for(i=1;;i++){scanf("%c",&B[i]);if(B[i]<32)break;}lenB=i-1;
	//scanf("%s",&A);lenA=strlen(A);
	//scanf("%s",&B);lenB=strlen(B);
	fgets(A+1,2000005,stdin);
	fgets(B+1,2000005,stdin);
	lenA=strlen(A+1)-1;
	lenB=strlen(B+1)-1;
}
void solve()
{
	for(i=2;i<=lenA;i++)
	{
		while(k && A[k+1]!=A[i])k=prefix[k];
		if(A[k+1]==A[i])k++;
		prefix[i]=k;
	}
	for(i=1;i<=lenB;i++)
	{
		while(q && A[q+1]!=B[i])q=prefix[q];
		if(A[q+1]==B[i])q++;
		if(q==lenA)v[++nr]=i-lenA;
	}
	printf("%d\n",nr);
	nr=nr<1001?nr:1000;
	for(i=1;i<=nr;i++)
		printf("%d ",v[i]);
}