Pagini recente » Cod sursa (job #575972) | Cod sursa (job #2576352) | Cod sursa (job #2771906) | Cod sursa (job #2128357) | Cod sursa (job #1955343)
// RABIN-KARP
// Made in Romania by Florin Haja
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int mod1 = 100007, mod2 = 100021, P = 73;
char a[2000005], b[2000005];
int fol[2000005];
int n, m, i, j;
int Hash1, Hash2, P1, P2;
int HashB1, HashB2, ns;
int main() {
f.getline(a, sizeof(a));
f.getline(b, sizeof(b));
n = strlen(a), m = strlen(b);
for (i = 0; i < n; i++)
a[i] -= 'A';
for (i = 0; i < m; i++)
b[i] -= 'A';
P1 = P2 = 1;
for (i = 0; i < n; i++) {
Hash1 = (Hash1 * P + a[i])%mod1;
Hash2 = (Hash2 * P + a[i])%mod2;
HashB1 = (HashB1 * P + b[i])%mod1;
HashB2 = (HashB2 * P + b[i])%mod2;
if (i) P1 = (P1*P)%mod1, P2 = (P2*P)%mod2;
}
if (n > m) {
g<<0;
return 0;
}
if (HashB1==Hash1 && HashB2==Hash2) fol[ns=1] = 0;
for (i = n; i < m; i++) {
HashB1 = (( (HashB1 - (b[i-n]*P1)%mod1 )+mod1 ) * P + b[i] ) %mod1;
HashB2 = (( (HashB2 - (b[i-n]*P2)%mod2 )+mod2 ) * P + b[i] ) %mod2;
if (HashB1==Hash1 && HashB2==Hash2) fol[++ns] = i-n+1;
}
g << ns << '\n';
for (i = 1; i <= min(ns,1000); i++)
g<<fol[i] << ' ';
return 0;
}