Cod sursa(job #331957)

Utilizator dya_ndmNanuti Diana-Maria dya_ndm Data 15 iulie 2009 22:26:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<stdio.h>      
#include<string.h>      
     
long num,n,m,sol[1005];      
char x[2000001],y[2000001];      
long kmpshift[2000001];;      
     
void preKMP(char x[],long n,long kmpshift[])
{      
long i,j;      
i=0;      
j=kmpshift[0]=-1;      
     
while(i<m)      
     {      
     while(j>-1 && x[i]!=x[j])      
          j=kmpshift[j];      
     ++i;++j;      
     if(x[i]==x[j])      
       kmpshift[i]=kmpshift[j];      
     else     
       kmpshift[i]=j;      
     }      
}      
     
void KMP()
{      
long i,j,l=0;      
preKMP(y,m,kmpshift);
i=j=0;      
while(i<n)      
     {      
     while(j>-1 && x[i]!=y[j])      
          j=kmpshift[j];      
     ++i;++j;      
     if(j>=m)      
       {    
       ++num;        
       if(num<=1000)      
         sol[++l]=i-j;      
       j=kmpshift[j];      
       }      
     }      
}      
     
int main()      
{      
freopen("strmatch.in","r",stdin);      
freopen("strmatch.out","w",stdout);      
char c;      
long i=0;      
scanf("%s",&y);      
scanf("%s",&x);      
n=strlen(x);      
m=strlen(y);      
KMP();
     
printf("%ld\n",num);      
for(i=1;i<=num;++i)      
   printf("%ld ",sol[i]);      
return 0;      
}