Cod sursa(job #3038893)

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

#define BASE (1LL<<15)
#define MOD 1000000007

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;
    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 (sum_check == window) ans.push_back(0);

    for (int i = 1; i + a.size() - 1 < b.size(); ++i) {
        window = ((window + MOD - b[i - 1] * (BASE * BASE) % MOD) * BASE + b[i + a.size() - 1]) % MOD;
        if (sum_check == window) ans.push_back(i);
    }

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

    return 0;
}