Pagini recente » Cod sursa (job #1780253) | Cod sursa (job #810840) | Cod sursa (job #3349081) | Cod sursa (job #1537527) | Cod sursa (job #3318080)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
const long long BASE = 100;
const long long MOD1 = 1000000007;
const long long MOD2 = 666013;
const char HASHER = '0';
char A[NMAX], B[NMAX];
long long powers[2][NMAX];
void PrecomputePowers(int n) {
powers[0][0] = 1;
powers[1][0] = 1;
for (int i = 1; i <= n; i++) {
powers[0][i] = (powers[0][i - 1] * BASE) % MOD1;
powers[1][i] = (powers[1][i - 1] * BASE) % MOD2;
}
}
int getMod(int mod_index) {
if(mod_index == 0) return MOD1;
return MOD2;
}
long long HashEntireString(const char s[], int n, int mod_index) {
int mod = getMod(mod_index);
long long h = 0;
for (int i = 0; i < n; i++)
h = (h + powers[mod_index][n-i-1] * (s[i] - HASHER)) % mod;
return h;
}
long long getNextHash(int current_hash, int n, char oldChar, char newChar, int mod_index) {
int mod = getMod(mod_index);
current_hash = (current_hash - powers[mod_index][n - 1] * (oldChar - HASHER)) % mod;
if (current_hash < 0) current_hash += mod;
current_hash = (current_hash * BASE) % mod;
current_hash = (current_hash + (newChar - HASHER)) % mod;
return current_hash;
}
vector<int> RabinKarp(const char a[NMAX], const char b[]) {
vector<int> positions;
int n = strlen(a), m = strlen(b);
long long hash_A_1 = HashEntireString(a, n, 0);
long long hash_A_2 = HashEntireString(a, n, 1);
long long current_hash_1 = HashEntireString(b, n, 0);
long long current_hash_2 = HashEntireString(b, n, 1);
if (hash_A_1 == current_hash_1 && hash_A_2 == current_hash_2)
positions.push_back(0);
for (int i = n; i < m; i++) {
current_hash_1 = getNextHash(current_hash_1, n, b[i-n], b[i], 0);
current_hash_2 = getNextHash(current_hash_2, n, b[i-n], b[i], 1);
if (current_hash_1 == hash_A_1 && current_hash_2 == hash_A_2)
positions.push_back(i - n + 1);
}
return positions;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> A >> B;
PrecomputePowers(strlen(A) + 1);
vector<int> ans = RabinKarp(A, B);
cout << ans.size() << "\n";
for (int i = 0; i < (int)ans.size(); i++)
cout << ans[i] << " ";
cout << "\n";
return 0;
}