Cod sursa(job #3295972)

Utilizator pkseVlad Bondoc pkse Data 10 mai 2025 12:08:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <vector>
#define base 512
#define mod 1'000'000'007
#define int long long
using namespace std;

signed h[2'000'005];
signed pow[2'000'005];
vector<int> ans;

int query(int st, int dr) {
    st ++;
    dr ++;
    return (h[dr] - h[st - 1] * pow[dr - st + 1] % mod + mod) % mod;
}

signed main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    
    string a, s; cin >> a >> s;
    h[1] = s[0];
    pow[0] = 1;
    for(int i = 1; i < s.size(); i ++) {
        h[i + 1] = 1ll * (h[i] * base % mod + s[i]) % mod;
        pow[i] = 1ll * pow[i - 1] * base % mod;
    }
    int hsh = 0;
    for(int i = 0; i < a.size(); i ++) {
        hsh = 1ll * hsh * base % mod + a[i];
    }
    for(int st = 0, dr = a.size() - 1; dr < s.size(); st ++, dr ++) {
        if(hsh == query(st, dr)) {
            ans.push_back(st);
        }
    }
    cout << ans.size() << '\n';
    int cnt = 0;
    for(auto i : ans) {
        cout << i << ' ';
        cnt ++;
        if(cnt == 1000)
            break;
    }
    // cout << '\n' << query(7, 9) << ' ' << hsh;
}