Cod sursa(job #3038913)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 27 martie 2023 21:53:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>

#define BASE 256
#define MOD 101

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

    std::string a, b;
    input >> a >> b;
    std::vector<int> ans;

    long long sum_check = 0;
    long long window = 0;

    int prod = 1;

    for (int i = 0; i < a.size(); ++i) {
        sum_check = (sum_check * BASE % MOD + a[i]) % MOD;
        window = (window * BASE % MOD + b[i]) % MOD;

        if (i > 0) prod = prod * BASE % MOD;
    }

    if (sum_check == window) ans.push_back(0);

    for (int i = 1; i + a.size() - 1 < b.size(); ++i) {
        window = ((window - b[i - 1] * prod) * BASE + b[i + a.size() - 1]) % MOD;
        if (window < 0) window += MOD;
        if (sum_check == window) {
            bool match = true;

            for (int j = 0; j < a.length() && match; ++j) {
                if (a[j] != b[i + j]) match = false;
            }
            if (match) ans.push_back(i);
        }
    }

    output << ans.size() << '\n';
    for (auto &x: ans) output << x << " ";

    return 0;
}