Cod sursa(job #331961)

Utilizator dya_ndmNanuti Diana-Maria dya_ndm Data 15 iulie 2009 22:48:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#include<string.h>
#define ct 2000005
char x[ct],y[ct];
long m,n,num,sol[1005],kmp[ct];

void prkmp()
{
int i,j;
i=0;
j=kmp[0]=-1;
while(i<m)
     {
     while(j>-1 && x[i]!=x[j])
          j=kmp[j];
     ++i;++j;
     if(x[i]==x[j])
       kmp[i]=kmp[j];
     else
       kmp[i]=j;
     }
}

void kMp()
{
int i,j,l;
prkmp();
i=j=l=0;
while(i<n)
     {
     while(j>-1 && x[j]!=y[i])
          j=kmp[j];
     ++i;++j;
     if(j>=m)
       {    
       ++num;        
       if(num<=1000)      
         sol[++l]=i-j;      
       j=kmp[j];
       }      
     }
}

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

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