Cod sursa(job #530146)
#include <cstdio>
#include <string>
using namespace std;
#define MAXN 2000001
#define MAX_MATCHES 1000
#define PRIME_MULT 73
#define PRIME_MOD 100007
char A[MAXN], B[MAXN];
int lenA, lenB, matches, indices[MAX_MATCHES];
void countIfMatch(int startB) {
for (int i=0;i<lenA;i++) {
if (A[i]!=B[startB+i]) {
return;
}
}
if (matches<MAX_MATCHES) {
indices[matches] = startB;
}
matches++;
}
int main()
{
int hashA, hashB, pow;
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", A, B);
lenA = strlen(A); lenB = strlen(B);
if (lenA > lenB) {
printf("0\n");
return 0;
}
hashA = A[0], hashB = B[0]; pow = 1;
for (int i = 1; i < lenA; i++) {
hashA = (hashA * PRIME_MULT + A[i]) % PRIME_MOD;
hashB = (hashB * PRIME_MULT + B[i]) % PRIME_MOD;
pow = (pow*PRIME_MULT) % PRIME_MOD;
}
if (hashA == hashB) {
countIfMatch(0);
}
for (int i = lenA; i < lenB; i++)
{
hashB = ((hashB - (B[i - lenA] * pow) % PRIME_MOD + PRIME_MOD) * PRIME_MULT + B[i]) % PRIME_MOD;
if (hashA == hashB) countIfMatch(i-lenA+1);
}
printf("%d\n", matches);
int limit = (matches<=MAX_MATCHES)?matches:MAX_MATCHES;
for (int i=0;i<limit;i++) {
printf("%d ",indices[i]);
}
printf("\n");
return 0;
}