Cod sursa(job #3258136)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 21 noiembrie 2024 10:55:42
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
/**
 *  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;
}