Pagini recente » Cod sursa (job #1528151) | preONI 2008 - Clasament Runda 3, Clasele 11-12 | Cod sursa (job #1738254) | Cod sursa (job #246119) | Cod sursa (job #2283944)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_MATCHES = 1000;
struct Hash {
int prime, mod, power, hash;
void buildFrom(const std::string& s, int n) {
hash = 0, power = 1;
for (int i = 0; i < n; ++i) {
hash = (1LL * hash * prime + s[i]) % mod;
if (i)
power = (power * prime) % mod;
}
}
void update(char toRemove, char toAdd) {
hash = ((hash - (toRemove * power) % mod + mod) * prime + toAdd) % mod;
}
friend bool operator == (const Hash& first, const Hash& second) {
return first.hash == second.hash;
}
};
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
std::string needle, haystack;
int matchCount = 0;
std::vector<int> matchPositions;
std::getline(std::cin, needle);
std::getline(std::cin, haystack);
std::vector<Hash> needleHash{ { 79, 10007 }, { 73, 666013 } };
std::vector<Hash> haystackHash{ { 79, 10007 }, { 73, 666013 } };
for (int i = 0; i < needleHash.size(); ++i) {
needleHash[i].buildFrom(needle, needle.size());
haystackHash[i].buildFrom(haystack, needle.size());
}
if (std::equal(needleHash.begin(), needleHash.end(), haystackHash.begin())) {
matchPositions.push_back(0);
++matchCount;
}
for (int i = needle.size(); i < haystack.size(); ++i) {
for (int j = 0; j < haystackHash.size(); ++j)
haystackHash[j].update(haystack[i - needle.size()], haystack[i]);
if (std::equal(needleHash.begin(), needleHash.end(), haystackHash.begin())) {
++matchCount;
if (matchCount < MAX_MATCHES)
matchPositions.push_back(i - needle.size() + 1);
}
}
std::cout << matchCount << "\n";
for (int pos: matchPositions)
std::cout << pos << " ";
return 0;
}