Cod sursa(job #213674)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 10 octombrie 2008 21:57:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<stdio.h>
#include<string.h>
long n,m,k,s[2000060],x[1005],i,l;
char a[2000060],b[2000060];
int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 gets(a);
 gets(b);
 n=strlen(a);
 m=strlen(b);
 for(i=n;i;--i)a[i]=a[i-1];
 a[n+1]=0;
 for(i=m;i;--i)b[i]=b[i-1];
 b[m+1]=0;
 k=0;
 s[1]=0;
 for(i=2;i<=n;++i)
    {
     while(k>0&&a[k+1]!=a[i])k=s[k];
     if(a[k+1]==a[i])++k;
     s[i]=k;
    }
 k=0;
 for(i=1;i<=m;++i)
    {
     while(k>0&&a[k+1]!=b[i])k=s[k];
     if(a[k+1]==b[i])++k;
     if(k==n){k=s[n];++l;
     if(l<=1000)x[l]=i-n;}
    }
 printf("%ld\n",l);
 if(l>1000)l=1000;
 for(i=1;i<=l;++i)
    printf("%ld ",x[i]);
 printf("\n");
 return 0;
}