Cod sursa(job #1552498)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 18 decembrie 2015 10:54:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#include <cstring>

using namespace std;
int nr,n,m,i,k,x[2000004],y[2000004];
char a[2000004],b[2000004];

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

   gets(a+1);gets(b+1);
   n=strlen(a+1);m=strlen(b+1);

   x[1]=0;
   for(i=2;i<=n;++i)
   {
        k=x[i-1];
        while(k && a[i]!=a[k+1]) k=x[k];
        if(a[i]==a[k+1]) x[i]=k+1;
        else x[i]=0;
   }

   for(i=1;i<=m;++i)
   {
       k=y[i-1];
       while(k && b[i]!=a[k+1]) k=x[k];
       if(b[i]==a[k+1]) y[i]=k+1;
       else y[i]=0;
       if(y[i]==n) ++nr;
   }
   int afs=0;
   printf("%d\n",nr);
   for(i=n;i<=m && afs<1000;++i) if(y[i]==n) {printf("%d ",i-n);afs++;}
   printf("\n");

   return 0;
}