Cod sursa(job #369037)

Utilizator dya_ndmNanuti Diana-Maria dya_ndm Data 26 noiembrie 2009 21:52:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
#include<string.h>
#define LMAX 2000005
long n,m,num,k[LMAX],s[1005];
char x[LMAX],y[LMAX];
void prekmp(long k[])
{
long i,j;
i=0;
j=-1;
k[0]=j;
while(i<m)
    {
    while(j!=-1 && x[i]!=x[j])
				 j=k[j];
	++i;
	++j;
	if(x[i]==x[j])
		k[i]=k[j];
	else
		k[i]=j;
    }
}

void kmp()
{
long i,j;
prekmp(k);
i=j=0;
while(i<n)
     {
     while(j!=-1 && x[j]!=y[i])
					 j=k[j];
	 ++i;
	 ++j;
	 if(j>=m)
	   {
	   ++num;
	   if(num<=1000)
		   s[num]=i-j;
	   j=k[j];
	   }
     }
}

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

scanf("%s",&x);
scanf("%s",&y);
n=strlen(y);
m=strlen(x);
kmp();
printf("%ld\n",num);
int i;
for(i=1;i<=num;++i)
	printf("%ld ",s[i]);
return 0;
}