Pagini recente » Cod sursa (job #1753962) | Cod sursa (job #2130420) | Cod sursa (job #2312878) | Cod sursa (job #2749683) | Cod sursa (job #3240496)
#include <bits/stdc++.h>
using namespace std;
const string FILE_NAME = "strmatch.";
ifstream fin(FILE_NAME + "in");
ofstream fout(FILE_NAME + "out");
#define CH2NR(ch) (ch - 'A' + 1)
constexpr int ALPHA_LEN = 'z' - 'a' + 1, MOD = 1e9 + 7;
vector<int> RK(const string &text, const string &pattern) {//Rabin-Karp
const int txtSize = text.length(), pattSize = pattern.length();
vector<int> alPow(max(txtSize, pattSize)); //pows of ALPHA_LEN
alPow[0] = 1;
for (size_t i = 1; i < alPow.size(); i++) {
alPow[i] = (1LL * alPow[i - 1] * ALPHA_LEN) % MOD;
}
int pattHash = 0;
for (int i = 0; i < pattSize; i++) {
pattHash = (pattHash + 1LL * CH2NR(pattern[i]) * alPow[i]) % MOD;
}
vector<int> txtHashAt(txtSize + 1);//[i]->txt hash in interval [0, i)
for (int i = 0; i < txtSize; i++) {
txtHashAt[i + 1] = (txtHashAt[i] + 1LL * CH2NR(text[i]) * alPow[i]) % MOD;
}
vector<int> ans;
for (int i = 0; i <= txtSize - pattSize; i++) {
int currHash = (txtHashAt[i + pattSize] - txtHashAt[i] + MOD) % MOD;
if (currHash == 1LL * pattHash * alPow[i] % MOD) {
ans.push_back(i);
}
}
return ans;
}
int main() {
string text, pattern;
getline(fin, pattern);
getline(fin, text);
vector<int> ans = RK(text, pattern);
fout << ans.size() << endl;
for (int it : ans) {
fout << it << ' ';
}
fout << endl;
fout.close();
return 0;
}