Cod sursa(job #409438)

Utilizator petrecgClinciu Glisca Petre petrecg Data 3 martie 2010 17:40:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#include <string.h>
char s[2000100],p[2000100];long m,n,i,x,k,urm[2000100],v[2000100];
void urmatorul()
{long k=0,i;
 urm[0]=0;
 for(i=2;i<=m;i++)
  {while(k>0&&p[k+1]!=p[i])k=urm[k];
   if(p[k+1]==p[i])k++;
   urm[i]=k;
  }
}

int main()
{x=0;
 freopen("strmatch.in","r",stdin);freopen("strmatch.out","w",stdout);
 scanf("%s",&p);
 scanf("%s",&s);
 n=strlen(s);m=strlen(p);
 for(i=n+1;i>0;i--)s[i]=s[i-1];
 for(i=m+1;i>0;i--)p[i]=p[i-1];
 urmatorul();
 for(i=1;i<=n;i++)
  {while(x>0&&p[x+1]!=s[i])x=urm[x];
   if(p[x+1]==s[i])x++;
   if(x==m)
    {k++;v[k]=i-m;x=urm[x];}
  }
 printf("%ld\n",k);
 if(k>1000)k=1000;
 for(i=1;i<=k;i++)printf("%ld ",v[i]);
 fclose(stdin);fclose(stdout);
 return 0;
}