Pagini recente » Cod sursa (job #597583) | Cod sursa (job #2570888) | Cod sursa (job #2550451) | Cod sursa (job #751098) | Cod sursa (job #3258136)
/**
* Worg
*/
#include <vector>
#include <fstream>
class StringMatcher {
private:
std::string pattern;
std::string text;
std::vector<int> automaton;
public:
StringMatcher(const std::string& _pattern, const std::string& _text) : pattern(_pattern), text(_text) {
build_automaton();
}
void build_automaton() {
automaton = std::vector<int>();
automaton.reserve(text.size());
int fail_id = -1;
automaton[0] = fail_id;
for (int i = 1; i < (int)pattern.size(); i++) {
while (fail_id > -1 && pattern[i] != pattern[fail_id + 1]) {
fail_id = automaton[fail_id];
}
if (pattern[i] == pattern[fail_id + 1]) {
fail_id += 1;
}
automaton[i] = fail_id;
}
}
std::vector<int> get_string_match_ids() {
std::vector<int> match_ids;
int fail_id = -1;
for (int i = 0; i < (int)text.size(); i++) {
while (fail_id > -1 && text[i] != pattern[fail_id + 1]) {
fail_id = automaton[fail_id];
}
if (text[i] == pattern[fail_id + 1]) {
fail_id += 1;
}
if (fail_id == (int)pattern.size() - 1) {
match_ids.push_back(i - (int)pattern.size() + 1);
fail_id = automaton[fail_id];
}
}
return match_ids;
}
};
int main() {
std::ifstream fin("strmatch.in");
std::string a, b;
fin >> a >> b;
fin.close();
StringMatcher string_matcher(a, b);
std::vector<int> match_ids = string_matcher.get_string_match_ids();
std::ofstream fout("strmatch.out");
fout << match_ids.size() << '\n';
for (int i = 0; i < std::min(1000, (int)match_ids.size()); i++) {
fout << match_ids[i] << " ";
}
fout.close();
return 0;
}