Cod sursa(job #629470)
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <math.h>
using namespace std;
#define MAX_LG 2000010
#define MAX_P 1000000000039
char s1[MAX_LG], s2[MAX_LG];
long long B, Bn, ns1, ns2, nr, rez[1001], base, hash;
char symb[256];
long long next_prime (long long x) {
int ok;
while (1) {
ok = 1;
for (int i = 2; i <= sqrt (x); i ++)
if (x % i == 0) {
ok = 0;
break;
}
if (ok)
return x;
x ++;
}
}
long long first_hash (char *s, int p, int u) {
long long pw = 1;
long long rez = 0;
for (int i = u; i >= p; i --) {
rez = (rez + (s[i] * pw) % MAX_P ) % MAX_P;
pw = (pw * B) % MAX_P;
}
Bn = pw / B;
return rez;
}
long long next_hash (char *s, int old_hash, int p, int u) {
long long new_hash;
new_hash = (old_hash - (s[p-1] * Bn) % MAX_P) % MAX_P;
if (new_hash < 0)
new_hash += MAX_P;
new_hash = (new_hash * B) % MAX_P;
new_hash = (new_hash + s[u]) % MAX_P;
}
long long det_base (char *s) {
long long nrsymb = 0;
for (int i = 0; s[i]; i ++)
if (!symb[s[i]]) {
nrsymb ++;
symb[s[i]] = 1;
}
return nrsymb;
}
int main () {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
fgets (s1, MAX_LG, stdin);
ns1 = strlen (s1) - 1;
s1[ns1] = 0;
fgets (s2, MAX_LG, stdin);
ns2 = strlen (s2) - 1;
s2[ns2] = 0;
puts (s1);
puts (s2);
B = next_prime (det_base (s2));
base = first_hash (s1, 0, ns1- 1);
hash = first_hash (s2, 5, ns1 + 4);
for (int i = 0; i < ns2 - ns1; i ++)
if (hash == base && strncmp (s1, s2 + i, ns1) == 0)
if (nr < 1000)
rez[nr++] = i;
printf ("%lld\n", nr);
for (int i = 0; i < nr; i ++)
printf ("%lld ", rez[i]);
return 0;
}