Cod sursa(job #445677)

Utilizator IlieeUngureanu Ilie Iliee Data 24 aprilie 2010 11:54:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>
#include<cstring>
#include<cctype>
#define L 2000010
char A[L],B[L];
int a,b,i,n,P[L],X[1010],cnt;
void read(), solve(),prefix(),KMP();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",A+1);A[0]='#';
	scanf("%s",B+1);B[0]='#';
	a=strlen(A+1);
	b=strlen(B+1);
}
void solve()
{
	for(i=1;i<=a;i++)if(!isalnum(A[i])){a=i;break;}
	for(i=1;i<=b;i++)if(!isalnum(B[i])){b=i;break;}
	prefix();
	KMP();
	n=1000<cnt?1000:cnt;
	printf("%d\n",cnt);
	for(i=1;i<=n;i++)
		printf("%d ",X[i]);
}	
void prefix()
{
	int k=0;
	for(i=2;i<=a;i++)
	{
		while(k&&A[k+1]!=A[i])
			k=P[k];
		if(A[k+1]==A[i])
			k++;
		P[i]=k;
	}
}
void KMP()
{
	int k=0;
	for(i=1;i<=b;i++)
	{
		while(k&&B[i]!=A[k+1])
			k=P[k];
		if(B[i]==A[k+1])
			k++;
		if(k==a)
		{
			cnt++;
			if(cnt<=1000)
				X[cnt]=i-a;
			k=P[k];
		}
	}
}