Cod sursa(job #504424)
#include <stdio.h>
#include <string.h>
const int maxn=2000010;
char A[maxn],B[maxn];
int i,a,b,pi[maxn],nr,sol[1001];
void citire()
{
A[0]=' '; scanf("%s",A+1); a=strlen(A)-1;
B[0]=' '; scanf("%s",B+1); b=strlen(B)-1;
}
void prefixe()
{
int k=0; pi[1]=0;
for(i=2;i<=b;i++)
{
while(k>0 && A[k+1]!=A[i])
k=pi[k];
if(A[k+1]==A[i])
k++;
pi[i]=k;
}
}
void kmp()
{
int q=0;
for(i=1;i<=b;i++)
{
while(q>0 && A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
q++;
if(q==a)
{
q=pi[q];
nr++;
if(nr<=1000) sol[nr]=i-a;
}
}
}
void afisare()
{
printf("%d\n",nr);
if(nr>1000) nr=1000;
for(i=1;i<=nr;i++)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
prefixe();
kmp();
afisare();
}