Cod sursa(job #3357797)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 15:00:44
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

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

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

    int n = a.length();
    int m = b.length();

    if (n == 0 || m == 0 || n > m) {
        output << 0 << '\n';
        return 0;
    }

    const long long base = 31;
    const long long mod = 1e9 + 9;
    long long hash_a = 0;
    long long hash_b = 0;
    long long pow_base = 1;

    for (int i = 0; i < n; ++i) {
        hash_a = (hash_a * base + (a[i] - 'a' + 1)) % mod;
        hash_b = (hash_b * base + (b[i] - 'a' + 1)) % mod;
        if (i > 0) pow_base = (pow_base * base) % mod;
    }

    if (hash_a == hash_b) ans.push_back(0);

    for (int i = n; i < m; ++i) {
        hash_b = (hash_b - (b[i - n] - 'a' + 1) * pow_base % mod + mod) % mod;
        hash_b = (hash_b * base + (b[i] - 'a' + 1)) % mod;

        if (hash_a == hash_b) {
            ans.push_back(i - n + 1);
        }
    }

    output << ans.size() << '\n';
    for (int i = 0; i < ans.size() && i < 1000; ++i) {
        output << ans[i] << " ";
    }

    return 0;
}