Cod sursa(job #409282)

Utilizator petrecgClinciu Glisca Petre petrecg Data 3 martie 2010 15:51:10
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#include <string.h>
char s[1000],p[1000];long m,n,i,x,k,urm[1000],v[1000];
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;}
  }
 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;
}