Pagini recente » Cod sursa (job #3170909) | Cod sursa (job #1585151) | Cod sursa (job #2824932) | Cod sursa (job #2907838) | Cod sursa (job #1273982)
// rabin-karp
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const int Nmax = 2000666;
string A, B;
const int P = 101;
const int mod1 = 1000003;
const int mod2 = 1000033;
int sol[1033];
int main()
{
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
f >> A >> B;
int M = A.length(), N = B.length();
if (M > N) {
g << 0 << '\n';
return 0;
}
B.push_back('_');
int hash1 = A[0], hash2 = A[0];
int HB1 = B[0], HB2 = B[0];
int P1 = 1, P2 = 1;
for (int i = 1; i < M; i++) {
hash1 = (hash1 * P + A[i]) % mod1;
hash2 = (hash2 * P + A[i]) % mod2;
HB1 = (HB1 * P + B[i]) % mod1;
HB2 = (HB2 * P + B[i]) % mod2;
P1 = (P1 * P) % mod1;
P2 = (P2 * P) % mod2;
}
int start = 0, i = M;
int answer = 0;
do {
if ((HB1 == hash1) && (HB2 == hash2)) { // match
answer++;
if (answer < 1000)
sol[answer] = start;
}
HB1 = (((HB1 - (B[start]*P1) % mod1 + mod1) * P) + B[i]) % mod1;
HB2 = (((HB2 - (B[start]*P2) % mod2 + mod2) * P) + B[i]) % mod2;
start++;
i++;
} while (i <= N);
g << answer << '\n';
for (int j = 1; (j <= answer) && (j <= 1000); j++) {
g << sol[j] << ' ';
}
if (answer)
g << '\n';
return 0;
}