Cod sursa(job #338680)

Utilizator crisojogcristian ojog crisojog Data 6 august 2009 15:43:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000005

long n,m,pos[1002],k;
long kmpshift[NMAX];
char x[NMAX],y[NMAX];
void prekmp()
{
	int i,j;
	j=kmpshift[1]=0;
	for(i=2;i<=n;++i)
	{
		while(j && x[j+1]!=x[i])
			j=kmpshift[j];
		if(x[i]==x[j+1])
			++j;
		kmpshift[i]=j;
	}
}
void kmp()
{
	long i,j=0;
	for(i=1;i<=m;++i)
	{
		while(j && y[i]!=x[j+1])
			j=kmpshift[j];
		if(x[j+1]==y[i])
			++j;
		if(j==n-1)
		{
			++k;
			if(k<=1000)
				pos[k]=i-n+1;
		}
	}
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	long i;
	gets(x+1);
	gets(y+1);
	for(n=1;x[n];++n);  
    for(m=1;y[m];++m);
	prekmp();
	kmp();
	printf("%ld\n",k);
	if(k>1000) k=1000;
	for(i=1;i<=k;++i)
		printf("%ld ",pos[i]);
	printf("\n");
		
	return 0;
}