Cod sursa(job #313984)

Utilizator dya_ndmNanuti Diana-Maria dya_ndm Data 10 mai 2009 11:45:51
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 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(char x[],char y[],long n,long m)   
{   
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;   
     ++num;   
     if(j>=m)   
       {   
       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(x,y,n,m);   
  
printf("%ld\n",num);   
for(i=1;i<=num;++i)   
   printf("%ld ",sol[i]);   
return 0;   
}