Cod sursa(job #3295903)

Utilizator pkseVlad Bondoc pkse Data 9 mai 2025 17:30:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <vector>
#define base 256
#define mod 1'000'000'007
#define int long long
using namespace std;

int h[2'000'005];
int 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] = (h[i] * base % mod + s[i]) % mod;
        pow[i] = pow[i - 1] * base % mod;
    }
    int hsh = 0;
    for(int i = 0; i < a.size(); i ++) {
        hsh = 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);
        }
        if(ans.size() == 1000)
            break;
    }
    cout << ans.size() << '\n';
    for(auto i : ans) {
        cout << i << ' ';
    }
    // cout << '\n' << query(7, 9) << ' ' << hsh;
}