Cod sursa(job #195292)
#include <fstream.h>
#define NM 2000001
#define MM 2000001
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m;
int pi[MM];
char a[NM],b[MM];
int poz[1001];
void comput()
{pi[0]=0;
int i,x=0;
for (i=1;i<n;i++)
{while (x>0 && a[x]!=a[i]) x=pi[x-1];
if (a[x]==a[i]) x++;
pi[i]=x;
}
}
void kmp()
{int i,x=0;
int nr=0;
for (i=0;i<m;i++)
{while (x>0 && a[x]!=b[i]) x=pi[x-1];
if (a[x]==b[i]) x++;
if (x==n) {nr++;
if (nr<=1000) poz[nr]=i-n+1;
x=pi[x-1];
}
}
fout<<nr<<'\n';
for (i=1;i<=nr&&i<=1000;++i)
fout<<poz[i]<<' ';
}
int main()
{fin>>a;
fin>>b;
n=strlen(a);
m=strlen(b);
comput();
kmp();
return 0;
}