Cod sursa(job #3151160)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 19 septembrie 2023 22:22:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <vector>
#include <fstream>

int main() {
    std::ifstream input("strmatch.in");
    std::ofstream output("strmatch.out");
    std::string a, b;

    input >> a >> b;

    std::string s = a + "#" + b;

    std::vector<int> prefix(s.size());
    prefix[0] = 0;
    for (int i = 1; i < s.size(); ++i) {
        int j = prefix[i - 1];
        while (j > 0 && s[j] != s[i]) j = prefix[j - 1];
        if (s[i] == s[j]) j++;
        prefix[i] = j;
    }

    std::vector<int> ans;

    int n = (int) a.size();

    for (int i = n + 1; i < s.size(); ++i) {
        if (prefix[i] == a.size()) ans.push_back(i - 2 * n);
    }

    output << ans.size() << '\n';

    for (int i = 0; i < std::min(1000, (int) ans.size()); ++i) output << ans[i] << ' ';

    return 0;
}