Pagini recente » Cod sursa (job #2762386) | Cod sursa (job #2133097) | Cod sursa (job #2166762) | Cod sursa (job #2688283) | Cod sursa (job #2772930)
#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
const string fname = "strmatch";
ifstream fin(fname + ".in");
ofstream fout(fname + ".out");
///************************
class RollingHash {
public:
RollingHash(const string &text) {
this->text = text;
}
vector<int> getMatchingIndexes(const string &pattern, const int &maxMatches) const noexcept {
vector<int> indexes;
indexes.reserve(maxMatches);
auto patternCode = getCode(pattern);
const int patternLen = pattern.size();
auto poweredBasePair = getPoweredBase(patternLen);
int poweredBase[] = {
poweredBasePair.first,
poweredBasePair.second
};
int match[] = {0, 0};
for (int i = 0; i < patternLen; i++) {
for (int j = 0; j < 2; j++) {
match[j] = (match[j] * kBase + text[i]) % kHashPrimes[j];
}
}
if (make_pair(match[0], match[1]) == patternCode) {
indexes.push_back(0);
}
for (int i = patternLen; i < (int)text.size(); i++) {
for (int j = 0; j < 2; j++) {
match[j] = ((match[j] - (poweredBase[j] * text[i - patternLen]) % kHashPrimes[j] + kHashPrimes[j])
* kBase + text[i]) % kHashPrimes[j];
}
if (make_pair(match[0], match[1]) == patternCode) {
indexes.push_back(i - patternLen + 1);
}
}
return indexes;
}
private:
const int kHashPrimes[2] = {100003, 666013};
static constexpr int kBase = 137;
string text;
pair<int, int> getCode(const string &pattern) const noexcept {
int match[] = {0, 0};
for (int i = 0; i < (int)pattern.size(); i++) {
for (int j = 0; j < 2; j++) {
match[j] = (match[j] * kBase + pattern[i]) % kHashPrimes[j];
}
}
return make_pair(match[0], match[1]);
}
pair<int, int> getPoweredBase(const int &len) const noexcept {
int poweredBase[] = {1, 1};
for (int i = 1; i < len; i++) {
for (int j = 0; j < 2; j++) {
poweredBase[j] = (poweredBase[j] * kBase) % kHashPrimes[j];
}
}
return make_pair(poweredBase[0], poweredBase[1]);
}
};
int main() {
string text, pattern;
fin >> pattern >> text;
const auto rh = new RollingHash(text);
auto ans = rh->getMatchingIndexes(pattern, 1e3);
fout << ans.size() << endl;
for (const int &nr : ans) {
fout << nr << ' ';
}
fout << endl;
return 0;
}