Pagini recente » Sandbox | Cod sursa (job #1781558)
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
class RollingHash {
public:
RollingHash(const string& text) : text_(text) {
matchings_.resize(kHashPrimes[0]);
}
void Preprocess(int length, int number_of_occurences) {
int powered_base[2] = {1, 1};
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < 2; j++) {
powered_base[j] = (powered_base[j] * kBase) % kHashPrimes[j];
}
}
int match[2] = {0, 0};
for (int i = 0; i < length; i++) {
for (int j = 0; j < 2; j++) {
match[j] = (match[j] * kBase + text_[i]) % kHashPrimes[j];
}
}
matchings_[match[0]][match[1]].push_back(0);
for (int i = length; i < (int)text_.size(); i++) {
for (int j = 0; j < 2; j++) {
match[j] = ((match[j] - (powered_base[j] * text_[i - length]) % kHashPrimes[j] +
kHashPrimes[j]) * kBase + text_[i]) % kHashPrimes[j];
}
if ((int)matchings_[match[0]].size() < number_of_occurences) {
matchings_[match[0]][match[1]].push_back(i - length + 1);
}
}
}
vector<int> GetIndexes(const string& pattern) {
int match[2] = {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 matchings_[match[0]][match[1]];
}
private:
const int kHashPrimes[2] = {100003, 666013};
static const int kBase = 137;
vector<unordered_map<int, vector<int>>> matchings_;
string text_;
};
int main() {
cin.sync_with_stdio(false);
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string pattern;
cin >> pattern;
string text;
cin >> text;
RollingHash hash(text);
hash.Preprocess(pattern.size(), 1000);
vector<int> answer = hash.GetIndexes(pattern);
cout << answer.size() << '\n';
for (int it : answer) {
cout << it << " ";
}
return 0;
}