Cod sursa(job #3300616)

Utilizator db_123Balaban David db_123 Data 17 iunie 2025 22:55:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

#define int long long

char A[2000006];
char B[2000006];
int mod1=100007;
int mod2=100021;
vector<int>v;

int32_t main()
{
    v.reserve(1000);
    fin.getline(A,2000006);
    fin.getline(B,2000006);
    int na=strlen(A);
    int nb=strlen(B);
    ///daca lenA>lenB => nu merge
    if(na>nb){
        fout<<0;
        return 0;
    }
    ///il hashuiesc pe A cu m1 si m2
    int64_t ha1=0,p1=1;
    int64_t ha2=0,p2=1;
    for(int i=0;i<na;i++){
        ha1=((int64_t)(ha1*73)+A[i])%mod1;
        ha2=((int64_t)(ha2*73)+A[i])%mod2;
        ///retin puterea max fol pt fiec hash
        if(i!=0){
            p1=(int64_t)(p1*73)%mod1;
            p2=(int64_t)(p2*73)%mod2;
        }
    }
    ///il hashuiesc pe B treptat cu m1 si m2
    ///fac pt primele na char din B ca sa am "baza" de le care plec
    int hb1=0;
    int hb2=0;
    for(int i=0;i<na;i++){
        hb1=((int64_t)(hb1*73)+B[i])%mod1;
        hb2=((int64_t)(hb2*73)+B[i])%mod2;

    }
    ///daca se potrivesc ambele prime hashuri
    if(ha1==hb1 && ha2==hb2){
        v.push_back(0);
    }
    ///trec prin restul din B
    for(int i=na;i<nb;i++){
        ///tai val primului ch si adaug inca unul la fin
        int val_ch_ex=(int64_t)(B[i-na]*p1)%mod1;//ce tai
        int val_hash_atm=hb1-val_ch_ex+mod1;//hashul cu pr ch taiat
        hb1=((int64_t)(val_hash_atm*73)+B[i])%mod1;//adaug noul ch

        val_ch_ex=(int64_t)(B[i-na]*p2)%mod2;//ce tai
        val_hash_atm=(hb2-val_ch_ex+mod2)%mod2;//hashul cu pr ch taiat
        hb2=((int64_t)(val_hash_atm*73)+B[i])%mod2;//adaug noul ch

        ///verif daca se pupa
        if(ha1==hb1 && ha2==hb2 && v.size()<1000){
            v.push_back(i-na+1);//bag poz de inceput a subsirului
        }
    }
    fout<<v.size()<<'\n';
    for(int i=0;i<v.size();i++){
        fout<<v[i]<<" ";
    }

    return 0;
}