Pagini recente » Cod sursa (job #3301430) | Monitorul de evaluare | Cod sursa (job #2479477) | Cod sursa (job #3347239) | Cod sursa (job #3318136)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
const long long BASE = 100;
const long long MOD = 1000000007;
const char HASHER = '0';
char A[NMAX], B[NMAX];
long long powers[NMAX];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void PrecomputePowers(int n) {
powers[0] = 1;
for (int i = 1; i <= n; i++)
powers[i] = (powers[i - 1] * BASE) % MOD;
}
long long HashEntireString(const char s[], int n) {
long long h = 0;
for (int i = 0; i < n; i++)
h = (h + powers[n - i - 1] * (s[i] - HASHER)) % MOD;
return h;
}
vector<int> RabinKarp(const char a[NMAX], const char b[]) {
vector<int> positions;
int n = strlen(a), m = strlen(b);
long long hash_A = HashEntireString(a, n);
long long current_hash = HashEntireString(b, n);
if (hash_A == current_hash)
positions.push_back(0);
for (int i = n; i < m; i++) {
current_hash = (current_hash - powers[n - 1] * (b[i - n] - HASHER)) % MOD;
if (current_hash < 0) current_hash += MOD;
current_hash = (current_hash * BASE) % MOD;
current_hash = (current_hash + (b[i] - HASHER)) % MOD;
if (current_hash == hash_A)
positions.push_back(i - n + 1);
}
return positions;
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
fin >> A >> B;
PrecomputePowers(strlen(A) + 1);
vector<int> ans = RabinKarp(A, B);
fout << ans.size() << "\n";
for (int i = 0; i < min((int)ans.size(), 1000); i++)
fout << ans[i] << " ";
fout << "\n";
return 0;
}