Pagini recente » Cod sursa (job #2118144) | Cod sursa (job #1441309) | Cod sursa (job #735910) | Cod sursa (job #3248338) | Cod sursa (job #1955311)
// 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];
bool fol[2000005];
int n, m, i, j;
int Hash1, Hash2, P1, P2;
int HashB1, HashB2, ns;
int main() {
f.getline(a+1, sizeof(a));
f.getline(b+1, sizeof(b));
n = strlen(a+1), m = strlen(b+1);
for (i = 1; i <= n; i++)
a[i] -= 'A';
for (i = 1; i <= m; i++)
b[i] -= 'A';
P1 = P2 = 1;
for (i = 1; 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>1) P1 = (P1*P)%mod1, P2 = (P2*P)%mod2;
}
if (n > m) {
g<<0;
return 0;
}
if (HashB1==Hash1 && HashB2==Hash2) fol[0] = 1, ns++;
for (i = n+1; 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[i-n] = 1, ns++;
}
g << ns << '\n';
ns = 0;
for (i = 0; i < m && ns < 1000; i++)
if (fol[i]) {
g << i << ' ';
ns++;
}
return 0;
}