Pagini recente » Cod sursa (job #2977050) | Cod sursa (job #851457) | Cod sursa (job #1815139) | Cod sursa (job #1149295) | Cod sursa (job #409438)
Cod sursa(job #409438)
#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;
}