Pagini recente » Cod sursa (job #582709) | Rezultatele filtrării | Monitorul de evaluare | Cod sursa (job #3208967) | Cod sursa (job #3247074)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
using i64 = long long;
using pii = pair<int, int>;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int N = 2e6 + 5;
pii hash_pat, _hash_text[N], *hash_text;
int pow1, pow2, ans;
string pat, text;
vector<int> occurences;
int main() {
fi >> pat >> text;
hash_text = _hash_text + 1;
occurences.reserve(1000);
// calculam hash_pat
for (int i = 0; i < pat.size(); ++i) {
hash_pat.x = (i64(hash_pat.x) * 128 + pat[i]) % MOD1;
hash_pat.y = (i64(hash_pat.y) * 128 + pat[i]) % MOD2;
}
// calculam hashuri partiale pentru text
for (int i = 0; i < text.size(); ++i) {
hash_text[i].x = (i64(hash_text[i - 1].x) * 128 + text[i]) % MOD1;
hash_text[i].y = (i64(hash_text[i - 1].y) * 128 + text[i]) % MOD2;
}
// pow1 = 128^(pat.size()) % MOD1
// pow2 = 128^(pat.size()) % MOD2
pow1 = pow2 = 1;
for (int i = 0; i < pat.size(); ++i) {
pow1 = i64(pow1) * 128 % MOD1;
pow2 = i64(pow2) * 128 % MOD2;
}
for (int i = 0; i + pat.size() - 1 < text.size(); ++i) {
pii window_hash; // hash(text[i..i+pat.size() - 1])
window_hash.x = (hash_text[i + pat.size() - 1].x - i64(hash_text[i - 1].x) * pow1) % MOD1;
if (window_hash.x < 0)
window_hash.x+= MOD1;
window_hash.y = (hash_text[i + pat.size() - 1].y - i64(hash_text[i - 1].y) * pow2) % MOD2;
if (window_hash.y < 0)
window_hash.y+= MOD2;
if (window_hash == hash_pat) {
ans+= 1;
if (occurences.size() < 1000)
occurences.push_back(i);
}
}
fo << ans << '\n';
for (auto i: occurences)
fo << i << ' ';
fo << '\n';
return 0;
}