Cod sursa(job #313980)

Utilizator dya_ndmNanuti Diana-Maria dya_ndm Data 10 mai 2009 11:40:50
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
#include<string.h>

long num,n,m,l,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;
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)
       {
       j=kmpshift[j];
       ++l;
       if(l<=1000)
         sol[l]=i-j;
       }
     }
}

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
char c;
long i=0;
scanf("%s\n",&y);
scanf("%s\n",&x);
n=strlen(x);
m=strlen(y);
KMP(x,y,n,m);
printf("%ld\n",l);
if(l>1000)
  l=1000;
for(i=1;i<=l;++i)
   printf("%ld ",sol[i]);
return 0;
}