Pagini recente » Cod sursa (job #1426617) | Cod sursa (job #820925) | Cod sursa (job #1085457) | Cod sursa (job #1152834) | Cod sursa (job #2582203)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
string pattern, text;
const int P = 73;
const int MOD1 = 1e9+9;
const int MOD2 = 1e9+21;
const int NMAX = 2000505;
int H_MOD1[NMAX], H_MOD2[NMAX];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> pattern >> text;
int N = (int) pattern.size(), M = (int) text.size();
int hashMod1 = 0L, hashMod2 = 0L, powN_MOD1 = 1, powN_MOD2 = 1;
for (int idx = 0; idx < N; idx++) {
hashMod1 = (1LL * hashMod1 * P + pattern[idx]) % MOD1;
hashMod2 = (1LL * hashMod2 * P + pattern[idx]) % MOD2;
powN_MOD1 = (1LL * powN_MOD1 * P) % MOD1;
powN_MOD2 = (1LL * powN_MOD2 * P) % MOD2;
}
for (int idx = 0; idx < M; idx++) {
H_MOD1[idx + 1] = (1LL * H_MOD1[idx] * P + text[idx]) % MOD1;
H_MOD2[idx + 1] = (1LL * H_MOD2[idx] * P + text[idx]) % MOD2;
}
int matches = 0;
vector<int> sol;
for (int st = 1; st <= M - N; st++) {
int currH_MOD1 = (H_MOD1[st + N - 1] + MOD1 - (1LL * H_MOD1[st - 1] * powN_MOD1) % MOD1) % MOD1;
int currH_MOD2 = (H_MOD2[st + N - 1] + MOD2 - (1LL * H_MOD2[st - 1] * powN_MOD2 % MOD2)) % MOD2;
if (hashMod1 == currH_MOD1 && hashMod2 == currH_MOD2) {
matches++;
if (matches <= 1000) {
sol.push_back(st);
}
}
}
cout << matches << "\n";
for (auto match : sol) {
cout << match - 1 << " ";
}
cout << "\n";
return 0;
}