Cod sursa(job #3334645)

Utilizator David_RadavoiRadavoi David Alexandru David_Radavoi Data 18 ianuarie 2026 19:57:56
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

string a, b;

#define MOD 50021
#define BAZA 71

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int egale(int poz){
    for (int i = 0; i < a.size(); i++){
        if (a[i] != b[i + poz]){
            return 0;
        }
    }
    return 1;
}

int main()
{
    fin >> a >> b;
    if (a.size() > b.size()){
        fout << "0";
        return 0;
    }
    int hashA = 0, B = 1;
    for (int i = 0; i < a.size(); i++){
        a[i] -= 'A';
        hashA = (hashA * BAZA + a[i]) % MOD;
        if (i > 0){
            B = (B * BAZA) % MOD;
        }
    }
    int hashB = 0;
    for (int i = 0; i < b.size(); i++){
        b[i] -= 'A';
    }
    for (int i = 0; i < a.size(); i++){
        hashB = (hashB * BAZA + b[i]) % MOD;
    }
    vector <int> rez;
    int nr = 0;
    if (hashA == hashB && egale(0) == 1){
        nr++;
        rez.push_back(0);
    }
    for (int i = a.size(); i < b.size(); i++){
        hashB = (((hashB - b[i - a.size()] * B) % MOD + MOD) * BAZA + b[i]) % MOD;
        if (hashA == hashB && egale(i - a.size() + 1)){
            nr++;
            rez.push_back(i - a.size() + 1);
        }
    }
    fout << nr << '\n';
    for (int i = 0; i < rez.size(); i++){
        fout << rez[i] << " ";
    }
    return 0;
}