Cod sursa(job #825741)
#include<fstream>
#include<string.h>
#define nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[nmax],b[nmax];
int p[nmax],poz[1005],k,n,m;
void prefix()
{
for(int i=2,q=0;i<=m;i++)
{
while(q && a[q+1]!=a[i])
q=p[q];
if(a[q+1]==a[i])
q++;
p[i]=q;
}
}
void kmp()
{
for(int i=1,q=0;i<=n;i++)
{
while(q && a[q+1]!=b[i])
q=p[q];
if(a[q+1]==b[i])
q++;
if(q==m)
{
q=p[m];
k++;
if(k<=1000)
poz[k]=i-m;
}
}
}
void afisare()
{
int i;
g<<k<<'\n';
if(k>1000)
k=1000;
for(i=1;i<=k;i++)
g<<poz[i]<<' ';
g<<'\n';
g.close();
}
void citire()
{
a[0]=b[0]=' ';
f>>a+1>>b+1;
m=strlen(a)-1;
n=strlen(b)-1;
f.close();
}
int main()
{
citire();
prefix();
kmp();
afisare();
return 0;
}