Cod sursa(job #3323801)

Utilizator boboc132Boboc Teodor boboc132 Data 19 noiembrie 2025 21:38:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <string>
#include <fstream>
using namespace std;

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

const int P=73;
const int MOD1=100007,MOD2=100021;
const int N_MAX=2000001;
int NA,NB;
string A,B;
int hashA1,hashA2;
int hash1,hash2;
int P1,P2;
int match[N_MAX],ind;

int main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);
    out.tie(NULL);
    in>>A>>B;
    NA=A.length();
    NB=B.length();

    P1=P2=1;
    for(int i=0;i<NA;i++){
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2=(hashA2*P+A[i])%MOD2;
        if(i!=0){
            P1=(P1*P)%MOD1;
            P2=(P2*P)%MOD2;
        }
    }
    
    for(int i=0;i<NA;i++){
        hash1=(hash1*P+B[i])%MOD1;
        hash2=(hash2*P+B[i])%MOD2;
    }

    if(hash1==hashA1 && hash2==hashA2){
        match[++ind]=0;
    }

    for(int i=NA;i<NB;i++){//i este sfarsitul ferestrei deci inceputul ferestrei este i-NA+1 un fel de (dr-st+1)
        hash1=((hash1-(B[i-NA]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
        hash2=((hash2-(B[i-NA]*P2)%MOD2+MOD2)*P+B[i])%MOD2;
        if(hash1==hashA1 && hash2==hashA2){
            match[++ind]=i-NA+1;
        }
    }
    out<<ind<<"\n";
    for(int i=1;i<=ind && i<=1000;i++){
        out<<match[i]<<" ";
    }
}