Cod sursa(job #761937)
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000010],t[2000010];
long fct[2000005],lgp,lgt,x,v[1005];
int main()
{
long i;
f.getline(p,2000005,'\n');
f.getline(t,2000005,'\n');
lgp=strlen(p);
lgt=strlen(t);
fct[0]=0;
for(i=1;i<lgp;i++){
x=fct[i-1];
while(x>0&&p[x]!=p[i])
x=fct[x-1];
if(p[x]==p[i])
x++;
fct[i]=x;}
x=0;
for(i=0;i<lgt;i++){
while(x>0&&t[i]!=p[x])
x=fct[x-1];
if(t[i]==p[x])
x++;
if(x==lgp){
v[++v[0]]=i-lgp+1;
x=fct[x-1];
if(v[0]==1000)
break;}}
g<<v[0]<<'\n';
for(i=1;i<=v[0];i++)
g<<v[i]<<' ';
f.close();
g.close();
return 0;
}