Cod sursa(job #3333276)

Utilizator abetAlbert Voiculescu abet Data 12 ianuarie 2026 17:48:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);
    string A, B;
    in >> A >> B;
    int m = A.size(), n = B.size();
    if (m > n) {
        out << 0 << "\n";
        return 0;
    }
    const int base1 = 131, base2 = 137;
    const int mod1 = 1000000007;
    const int mod2 = 1000000009;
    int hashA1 = 0, hashB1 = 0;
    int hashA2 = 0, hashB2 = 0;
    int power1 = 1, power2 = 1;
    for (int i = 0; i < m; i++) {
        hashA1 = (1LL * hashA1 * base1 + (unsigned char)A[i]) % mod1;
        hashB1 = (1LL * hashB1 * base1 + (unsigned char)B[i]) % mod1;
        hashA2 = (1LL * hashA2 * base2 + (unsigned char)A[i]) % mod2;
        hashB2 = (1LL * hashB2 * base2 + (unsigned char)B[i]) % mod2;
        if (i < m - 1) {
            power1 = (1LL * power1 * base1) % mod1;
            power2 = (1LL * power2 * base2) % mod2;
        }
    }
    vector<int> pos;
    long long total = 0;
    for (int i = 0; i <= n - m; i++) {
        if (hashA1 == hashB1 && hashA2 == hashB2) {
            total++;
            if ((int)pos.size() < 1000)
                pos.push_back(i);
        }
        if (i + m < n) {
            hashB1 = (hashB1 - 1LL * (unsigned char)B[i] * power1 % mod1 + mod1) % mod1;
            hashB1 = (1LL * hashB1 * base1 + (unsigned char)B[i + m]) % mod1;
            hashB2 = (hashB2 - 1LL * (unsigned char)B[i] * power2 % mod2 + mod2) % mod2;
            hashB2 = (1LL * hashB2 * base2 + (unsigned char)B[i + m]) % mod2;
        }
    }

    out << total << "\n";
    for (int x : pos) out << x << " ";
    out << "\n";

    return 0;
}