Cod sursa(job #3300590)

Utilizator deliaandreeaddelia andreea deliaandreead Data 17 iunie 2025 16:22:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 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=100007;
int mod2=100021;
int b=73;
vector<int>v;

int 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
    int ha1=0,p1=1;
    int ha2=0,p2=1;
    for(int i=0;i<na;i++){
        ha1=(ha1*b+A[i])%mod1;
        ha2=(ha2*b+A[i])%mod2;
        ///retin puterea max fol pt fiec hash
        if(i!=0){
            p1=(p1*b)%mod1;
            p2=(p2*b)%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=(hb1*b+B[i])%mod1;
        hb2=(hb2*b+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;//hashul cu pr ch taiat
        hb1=(val_hash_atm*b+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*b+B[i])%mod2;//adaug noul ch

        ///verif daca se pupa
        if (ha1==hb1 && ha2==hb2 && strncmp(A, B+i-na+1, na==0)){
            if (v.size()<1000)
                v.push_back(i-na+1);
        }
    }
    fout<<v.size()<<'\n';
    for(int i=0;i<v.size();i++)
        fout<<v[i]<<" ";

    return 0;
}