Cod sursa(job #2937487)

Utilizator cristiWTCristi Tanase cristiWT Data 10 noiembrie 2022 15:55:51
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

#define NMAX 2000010
#define ll long long

using namespace std;

const int MOD = 1e9 + 9, p = 31;

string A, B;
ll Hash[NMAX];

ll compute_hash(const string& s) {
    ll val = 0, P = 1;
    for (auto ch: s) {
        val = (val + (ch - 'A' + 1) * P) % MOD;
        P = (P * p) % MOD;
    }
    return val;
}

ll inv(ll x) {
    ll P = x, b = MOD - 2, ans = 1;
    while (b) {
        if (b % 2)
            ans = (1LL * ans * P) % MOD;
        P = (1LL * P * P) % MOD;
        b /= 2;
    }
    return ans;
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> A >> B;
    if (A.size() > B.size()) {
        cout << 0;
        return 0;
    }

    ll hashA = compute_hash(A);
    string crt;
    for (int i = 0; i < B.size(); i++) {
        crt += B[i];
        Hash[i + 1] = compute_hash(crt);
    }

    ll aux = compute_hash("CAB");

    vector<int> ans;
    ll P = 1, M = B.size() - A.size() + 1;
    for (int i = 0; i < M; i++) {
        ll crtHash = (Hash[i + A.size()] - Hash[i] + MOD) % MOD;
        crtHash = (crtHash * inv(P)) % MOD;
        P = (P * p) % MOD;
        if (crtHash == hashA)
            ans.push_back(i);
    }

    cout << ans.size() << '\n';
    for (int i = 0; i < min((int)ans.size(), 1000); i++)
        cout << ans[i] << ' ';
}