Cod sursa(job #340374)
#include <cstdio>
#include <cstring>
#define MAX_N 2000005
#define MOD 100007
#define P 73
int match[MAX_N], nrm;
char A[MAX_N], B[MAX_N];
int main()
{
freopen("strmatch.in","rt",stdin);
freopen("strmatch.out","wt",stdout);
scanf("%s\n%s",A, B);
int N = strlen(A);
int M = strlen(B);
int h1 = 0, P1 = 1, H1 = 0;
for(int i = 0; i < N; ++i)
{
h1 = (h1*P + A[i]) % MOD;
H1 = (H1*P + B[i]) % MOD;
if(i)
P1 = (P1 * P) % MOD;
}
if(H1 == h1)
match[++nrm] = 1;
fprintf(stderr, "%d %d\n", h1, H1);
for(int i = N; i < M; ++i)
{
H1 = ((H1 - (B[i-N]*P1) % MOD + MOD)*P + B[i]) % MOD;
if(H1 == h1)
match[++nrm] = i - N + 1;
fprintf(stderr,"%d ",H1);
}
printf("%d\n",nrm);
for(int i = 1; i <= nrm && i <= 1000; ++i)
printf("%d ", match[i]);
}