Cod sursa(job #819293)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
#define mod1 666013
#define mod2 100007
char A[2000001], B[2000001];
int cod1A = 0, cod2A = 0, cod1B = 0, cod2B = 0;
int g1 = 1, g2 = 1, v[2000001];
ifstream in("strmatch.in"); ofstream out("strmatch.out");
void strVal(char *A, int n, int &cod1A, int &cod2A)
{
int i;
for (i=0;i<n;i++)
{
cod1A = (cod1A*73 + A[i])%mod1;
cod2A = (cod2A*73 + A[i])%mod2;
}
}
void gradVal(char *A, int &g1, int &g2)
{
int i;
for (i=1;i<strlen(A);i++)
{
g1 = (g1*73)%mod1;
g2 = (g2*73)%mod2;
}
}
int main()
{
in>>A>>B;
int nA = strlen(A), nB = strlen(B), i;
if (nA > nB)
{
out<<"0\n";
return 0;
}
strVal(A, nA, cod1A, cod2A);
gradVal(A, g1, g2);
strVal(B, nA, cod1B, cod2B);
int cnt = 0;
if (cod1A == cod1B && cod2A == cod2B)
v[++cnt] = 0;
for (i=nA; i<nB; i++)
{
cod1B = ((cod1B - (B[i - nA] * g1) % mod1 + mod1) * 73 + B[i]) % mod1;
cod2B = ((cod2B - (B[i - nA] * g2) % mod2 + mod2) * 73 + B[i]) % mod2;
if (cod1A == cod1B && cod2A == cod2B)
v[++cnt] = i-nA+1;
}
out<<cnt<<"\n";
for (i=1; i<=cnt && i<=1000; i++)
out<<v[i]<<" ";
return 0;
}