Cod sursa(job #561220)
#include <stdio.h>
#include <string.h>
#define Dim 2000010
int M,N,i,k,sol;
int L[Dim],v[1002];
char S[Dim],P[Dim];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(P+1,Dim,stdin);
fgets(S+1,Dim,stdin);
P[0]='!';
S[0]='!';
M=strlen(P)-1;
if(P[M]=='\n') P[M--]='\0';
N=strlen(S)-1;
if(S[N]=='\n') S[N--]='\0';
memset(L,0,sizeof(L));
k=0;
L[1]=0;
for(i=2;i<=M;i++)
{
while(k>0&&P[k+1]!=P[i]) k=L[k];
if(P[k+1]==P[i]) k++;
L[i]=k;
}
sol=0;
memset(v,0,sizeof(v));
k=0;
for(i=1;i<=N;i++)
{
while(k>0&&P[k+1]!=S[i]) k=L[k];
if(P[k+1]==S[i]) k++;
if(k==M)
{
sol++;
if(sol<1001) v[sol]=i-k;
k=L[k];
}
}
printf("%d\n",sol);
if(sol>1000) sol=1000;
for(i=1;i<=sol;i++)
printf("%d ",v[i]);
printf("\n");
return 0;
}