Cod sursa(job #3363192)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 12:25:45
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 9;
const int B = 67;

vector<int> h;

int lgpow(int a, int n) {
    a %= MOD;
    n %= MOD;
    int p = 0;
    for (; n; n >>= 1) {
        if (n & 1)
            p = p * a % MOD;
        a = a * a % MOD;
    }
    return p;
}

int invMod(int a) {
    return lgpow(a, MOD - 2);
}

int get(int i, int j) {
    return int(1LL * ((h[j] - h[i-1]) % MOD) * invMod(lgpow(B, i - 1)));
}

signed main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
#endif

    vector<int> mapare(128);
    for (int i = 'a'; i < 'z'; ++i)
        mapare[i] = i - 'a';
    for (int i = 'A'; i < 'Z'; ++i)
        mapare[i] = i - 'A' + 26;
    for (int i = 0; i < 9; ++i)
        mapare[i] = i + 52;

    string a, b; cin >> a >> b;
    int hashA = 0;
    for (int i = 0; i < int(a.size()); ++i) {
        hashA = int((hashA + 1LL * mapare[a[i]] * lgpow(B, i) % MOD) % MOD);
    }

    h.resize(b.size());
    h[0] = int(1LL * mapare[b[0]] * invMod(B) % MOD);
    for (int i = 1; i < int(h.size()); ++i) {
        h[i] = int((h[i-1] + 1LL * mapare[b[i]] * lgpow(B, i - 1) % MOD) % MOD);
    }
    
    vector<int> ans;
    for (int i = 0; i < int(b.size()); ++i) {
        if (get(i, i + int(a.size()) - 1) == hashA)
            ans.push_back(i + 1);
    }

    cout << ans.size() << '\n';
    for (auto& i : ans) cout << i << ' ';
    cout << '\n';

    return 0;
}