Cod sursa(job #957853)
#include <fstream>
#include <cstring>
#define size 2000002
using namespace std;
char P[size], T[size];
int m, n, i, d=52, q=53, x, v[1001];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int putere(int d, int m)
{
int p=1;
for(int i=1;i<=m-1;i++)
p=(p*d)%q;
return p;
}
int match(int k)
{
for(int i=0;i<=m-1;i++)
if(P[i]!=T[k+i])
return 0;
return 1;
}
void RK(int d, int q)
{
int h=putere(d, m);
int p=0, t=0;
for(int i=0;i<=m-1;i++)
{
p=(p*d+P[i])%q;
t=(t*d+T[i])%q;
}
for(int i=0;i<=n-m;i++)
{
if(t==p&&match(i))
v[++x]=i;
t=(t+q*d-T[i]*h)%q;
t=(t*d+T[i+m])%q;
}
}
int main()
{
fin>>P>>T;
n=strlen(T); m=strlen(P);
RK(d, q);
fout<<x<<'\n';
if(x>1000)
x=1000;
for(i=1;i<=x;i++)
fout<<v[i]<<' ';
fout<<'\n';
return 0;
}