Pagini recente » Cod sursa (job #613410) | Cod sursa (job #126246) | Cod sursa (job #1018124) | Cod sursa (job #409685) | Cod sursa (job #2456899)
#include <fstream>
#include <string>
#include <vector>
std::vector<int> computePrefix(const std::string &s) {
std::vector<int> prefix(s.size(), -1);
int k = -1;
for (int i = 1; i < s.size(); i++) {
while (k != -1 && s[k + 1] != s[i]) {
k = prefix[k];
}
if (s[k + 1] == s[i]) {
k = k + 1;
}
prefix[i] = k;
}
return prefix;
}
std::vector<int> solve(const std::string &pattern, const std::string &text) {
size_t n = text.size(), p = pattern.size();
std::vector<int> occurrences;
auto prefix = computePrefix(pattern);
int k = -1;
for (int i = 0; i < text.size(); i++) {
while (k != -1 && pattern[k + 1] != text[i]) {
k = prefix[k];
}
if (pattern[k + 1] == text[i]) {
k = k + 1;
}
if (k == pattern.size() - 1) {
occurrences.push_back(i - pattern.size() + 1);
k = prefix[k];
}
}
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';
}