Pagini recente » Cod sursa (job #1043071) | Cod sursa (job #2334025) | Cod sursa (job #1656005) | Cod sursa (job #1894467) | Cod sursa (job #1787551)
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
class RollingHash {
public:
RollingHash(const string& text) : text_(text) {
was_preprocessed_ = false;
}
void Preprocess(int length, int max_index_count) {
was_preprocessed_ = true;
vector<pair<int, int>> codes = GetCodes(length);
int current_index = 0;
for (pair<int, int> code : codes) {
AddIndex(code.first, code.second, current_index, max_index_count);
current_index++;
}
}
pair<int, vector<int>> GetMatchingIndexes(const string& pattern, int max_index_count) {
int count = 0;
vector<int> indexes;
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];
}
}
if (was_preprocessed_) {
long long pattern_code = GetCombinedCode(match[0], match[1]);
return {count_[pattern_code], matchings_[pattern_code]};
}
int length = pattern.size();
pair<int, int> pattern_code = {match[0], match[1]};
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];
}
}
match[0] = match[1] = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j < 2; j++) {
match[j] = (match[j] * kBase + text_[i]) % kHashPrimes[j];
}
}
if (make_pair(match[0], match[1]) == pattern_code) {
count++;
indexes.push_back(0);
}
return {count, indexes};
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 (make_pair(match[0], match[1]) == pattern_code) { */
/* count++; */
/* if ((int)indexes.size() < max_index_count) { */
/* indexes.push_back(i - length + 1); */
/* } */
/* } */
}
return {count, indexes};
}
private:
const int kHashPrimes[2] = {100003, 666013};
static const int kBase = 137;
bool was_preprocessed_;
string text_;
unordered_map<long long, vector<int>> matchings_;
unordered_map<long long, int> count_;
long long GetCombinedCode(int x, int y) {
return 1LL * x * kHashPrimes[1] + y;
}
void AddIndex(int match0, int match1, int index, int max_index_count) {
long long combinedCode = GetCombinedCode(match0, match1);
count_[combinedCode]++;
if ((int)matchings_[combinedCode].size() < max_index_count) {
matchings_[combinedCode].push_back(index);
}
}
vector<pair<int, int>> GetCodes(int length) {
vector<pair<int, int>> codes;
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];
}
}
/* codes.push_back({match[0], match[1]}); */
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];
}
codes.push_back({match[0], match[1]});
}
}
};
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); */
pair<int, vector<int>> answer = hash.GetMatchingIndexes(pattern, 1000);
cout << answer.first << '\n';
for (int it : answer.second) {
cout << it << " ";
}
return 0;
}