Cod sursa(job #3352743)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 1 mai 2026 01:20:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define int long long
const int p = 131;
const int mod = 1000000007;
const int NMAX = 2000000;
int power[NMAX + 5];
int fast_pow(int a, int b) {
    int ans = 1;
    a %= mod;
    while (b) {
        if (b % 2) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return ans;
}
signed main() {
    string a, b;
    fin>>a>>b;
    if (a.size() > b.size()) {
        fout<<0<<"\n";
        return 0;
    }
    power[0] = 1;
    for (int i = 1; i <= b.size(); i++) {
        power[i] = (power[i - 1] * p) % mod;
    }
    int inv_p = fast_pow(p, mod - 2);
    int hash_verif = 0, hash_curr = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        hash_verif = (hash_verif + power[i] * (int)a[i]) % mod;
        hash_curr = (hash_curr + power[i] * (int)b[i]) % mod;
    }
    vector<int> pos;
    if (hash_curr == hash_verif) {
        pos.push_back(0);
    }

    for (int i = (int)a.size(); i < (int)b.size(); i++) {
        int left = i - (int)a.size();
        hash_curr = (hash_curr - (int)b[left] + mod) % mod;
        hash_curr = (hash_curr * inv_p) % mod;
        hash_curr = (hash_curr + power[(int)a.size() - 1] * (int)b[i]) % mod;
        if (hash_curr == hash_verif) {
            pos.push_back(left + 1);
        }
    }
    fout<<pos.size()<<'\n';
    int limit = min((int)pos.size(), 1000LL);
    for (int i = 0; i < limit; i++) {
        fout << pos[i]<<' ';
    }
    fout << '\n';
}