Cod sursa(job #3357900)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 19:39:19
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 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;

    const int MOD1 = 1000000007;
    const int MOD2 = 1000000009;
    const int BASE = 31;

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

    if (n > m) {
        output << "0\n";
        return 0;
    }

    long long hash_a1 = 0, hash_a2 = 0;
    long long hash_b1 = 0, hash_b2 = 0;
    long long pow1 = 1, pow2 = 1;

    for (int i = 0; i < n; i++) {
        hash_a1 = (hash_a1 * BASE + (a[i] - 'a' + 1)) % MOD1;
        hash_a2 = (hash_a2 * BASE + (a[i] - 'a' + 1)) % MOD2;

        hash_b1 = (hash_b1 * BASE + (b[i] - 'a' + 1)) % MOD1;
        hash_b2 = (hash_b2 * BASE + (b[i] - 'a' + 1)) % MOD2;

        if (i < n - 1) {
            pow1 = (pow1 * BASE) % MOD1;
            pow2 = (pow2 * BASE) % MOD2;
        }
    }

    if (hash_a1 == hash_b1 && hash_a2 == hash_b2) {
        ans.push_back(0);
    }

    for (int i = n; i < m; i++) {
        hash_b1 = (hash_b1 - (b[i - n] - 'a' + 1) * pow1 % MOD1 + MOD1) % MOD1;
        hash_b1 = (hash_b1 * BASE + (b[i] - 'a' + 1)) % MOD1;

        hash_b2 = (hash_b2 - (b[i - n] - 'a' + 1) * pow2 % MOD2 + MOD2) % MOD2;
        hash_b2 = (hash_b2 * BASE + (b[i] - 'a' + 1)) % MOD2;

        if (hash_a1 == hash_b1 && hash_a2 == hash_b2) {
            ans.push_back(i - n + 1);
        }
    }

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

    return 0;
}