Cod sursa(job #409418)

Utilizator petrecgClinciu Glisca Petre petrecg Data 3 martie 2010 17:23:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 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=-1,x;
 urm[0]=0;
 for(x=1;x<m;x++)
  {while(k>0&&p[k+1]!=p[x])k=urm[k];
   if(p[k+1]==p[x])k++;
   urm[x]=k;
  }
}

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