Cod sursa(job #3333267)

Utilizator David_RadavoiRadavoi David Alexandru David_Radavoi Data 12 ianuarie 2026 17:34:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <vector>
#include <string>

using namespace std;

string a, b;

#define MOD1 50021
#define MOD2 50023
#define BAZA 26

int main()
{
    cin >> a >> b;
    if (a.size() > b.size()){
        cout << "0";
        return 0;
    }
    int hashA1 = 0, hashA2 = 0, B1 = 1, B2 = 1;
    for (int i = 0; i < a.size(); i++){
        hashA1 = (hashA1 * BAZA + a[i]) % MOD1;
        hashA2 = (hashA2 * BAZA + a[i]) % MOD2;
        if (i > 0){
            B1 = (B1 * BAZA) % MOD1;
            B2 = (B2 * BAZA) % MOD2;
        }
    }
    int hashB1 = 0, hashB2 = 0;
    for (int i = 0; i < a.size(); i++){
        hashB1 = (hashB1 * BAZA + b[i]) % MOD1;
        hashB2 = (hashB2 * BAZA + b[i]) % MOD2;
    }
    vector <int> rez;
    int nr = 0;
    if (hashA1 == hashB1 && hashA2 == hashB2){
        nr++;
        rez.push_back(0);
    }
    for (int i = a.size(); i < b.size(); i++){
        hashB1 = (((hashB1 - b[i - a.size()] * B1) % MOD1 + MOD1) * BAZA + b[i]) % MOD1;
        hashB2 = (((hashB2 - b[i - a.size()] * B2) % MOD2 + MOD2) * BAZA + b[i]) % MOD2;
        if (hashA1 == hashB1 && hashA2 == hashB2){
            nr++;
            rez.push_back(i - a.size() + 1);
        }
    }
    cout << nr << '\n';
    for (int i = 0; i < rez.size(); i++){
        cout << rez[i] << " ";
    }
    return 0;
}