Pagini recente » Cod sursa (job #2357529) | Cod sursa (job #2633420) | Cod sursa (job #1037365) | Cod sursa (job #2067142) | Cod sursa (job #2456867)
#include <fstream>
#include <queue>
#include <string>
#include <vector>
const long long R1 = 100007;
const long long R2 = 100021;
const long long B = 73;
struct slidingHash {
long long value1, value2, basePowR1, basePowR2;
std::queue<long long> digits;
slidingHash(const std::string &s, const int windowLen) {
this->basePowR1 = this->basePowR2 = 1;
this->value1 = this->value2 = 0;
for (int i = 0; i < windowLen && i < s.size(); i++) {
auto d = static_cast<long long>(s[i]);
this->digits.push(d);
this->value1 = (this->value1 * B + d) % R1;
this->value2 = (this->value2 * B + d) % R2;
if (i) {
this->basePowR1 = (this->basePowR1 * B) % R1;
this->basePowR2 = (this->basePowR2 * B) % R2;
}
}
}
void slideLeft(char c) {
long long dms = this->digits.front();
this->digits.pop();
long long dls = static_cast<long long>(c);
this->digits.push(dls);
this->value1 =
(((this->value1 - dms * this->basePowR1) % R1 + R1) * B + dls) % R1;
this->value2 =
(((this->value2 - dms * this->basePowR2) % R2 + R2) * B + dls) % R2;
}
bool equal(slidingHash &other) {
return this->value1 == other.value1 && this->value2 == other.value2;
}
};
std::vector<int> solve(const std::string &pattern, const std::string &text) {
size_t n = text.size(), p = pattern.size();
std::vector<int> occurrences;
slidingHash slideP(pattern, p), slideT(text, p);
if (slideP.equal(slideT)) {
occurrences.push_back(0);
}
for (int i = p + 1; i < n; i++) {
slideT.slideLeft(text[i]);
if (slideP.equal(slideT)) {
occurrences.push_back(i - p + 1);
}
}
return occurrences;
}
void read(std::string &pattern, std::string &text);
void write(const std::vector<int> &occurrences);
int main() {
std::string pattern, text;
read(pattern, text);
auto occurrences = solve(pattern, text);
write(occurrences);
return 0;
}
void read(std::string &pattern, std::string &text) {
std::ifstream fin("strmatch.in");
fin >> pattern >> text;
}
void write(const std::vector<int> &occurrences) {
std::ofstream fout("strmatch.out");
int count = 1000;
fout << occurrences.size() << '\n';
for (auto i : occurrences) {
fout << i << ' ';
count--;
if (!count) {
break;
}
}
fout << '\n';
}