Cod sursa(job #3300588)

Utilizator deliaandreeaddelia andreea deliaandreead Data 17 iunie 2025 15:50:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>


using namespace std;

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

char A[2000006];
char B[2000006];
int mod1=999983;
int mod2=999979;
vector<int>v;

int main()
{
    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
    int ha1=0,p1=1;
    int ha2=0,p2=1;
    for(int i=0;i<na;i++){
        ha1=(ha1*73+A[i])%mod1;
        ha2=(ha2*73+A[i])%mod2;
        ///retin puterea max fol pt fiec hash
        if(i!=0){
            p1=(p1*73)%mod1;
            p2=(p2*73)%mod2;
        }
    }
    ///il hashuiesc pe B treptat cu m1 si m2
    ///fac pt primele na char din B
    int hb1=0;
    int hb2=0;
    for(int i=0;i<na;i++){
        hb1=(hb1*73+B[i])%mod1;
        hb2=(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=(B[i-na]*p1)%mod1;//ce tai
        int val_hash_atm=(hb1-val_ch_ex+mod1)%mod1;//hashul cu pr ch taiat
        hb1=(val_hash_atm*73+B[i])%mod1;//adaug noul ch

        val_ch_ex=(B[i-na]*p2)%mod2;//ce tai
        val_hash_atm=(hb2-val_ch_ex+mod2)%mod2;//hashul cu pr ch taiat
        hb2=(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;
}