Cod sursa(job #2969240)

Utilizator LucaT2Tasadan Luca LucaT2 Data 22 ianuarie 2023 19:09:46
Problema Potrivirea sirurilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;
#define ull unsigned long long
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[2000001],b[2000001],la,lb;
ull n,sol[2000001];
#define M 100007
#define M1 100021


void citire()
{
    fin>>a;
    fin.get();
    fin>>b;
    la=strlen(a);
    lb=strlen(b);
}

void rabinkarp()
{
    ull ha=0,hb=0,ha1=0,hb1=0;
    ull p=73;
    ull p1=1,p2=1;
    for(ull i=0;i<la;i++){
        ha=(ha*p+a[i])%M;
        ha1=(ha1*p+a[i])%M1;

        if(i!=0){
            p1=(p1*p)%M;
            p2=(p2*p)%M1;
        }
    }
    for(ull i=0;i<la;i++){
        hb=(hb*p+b[i])%M;
        hb1=(hb1*p+b[i])%M1;
    }
    if(la>lb)
    {
        fout<<0;
        return ;
    }
    //fout<<ha<<" "<<ha1<<" "<<hb<<" "<<hb1<<"\n";
    if(ha==hb && ha1==hb1){
        sol[0]=1;
        n++;
    }

   // fout<<p<<" "<<p1<<" "<<p2<<"\n";
    for(ull i=la;i<lb;i++)
    {
        hb=((hb-(b[i-la]*p1)%M+M)*p+b[i])%M;
        hb1=((hb1-(b[i-la]*p2)%M1+M1)*p+b[i])%M1;
        if(ha==hb && ha1==hb1)
            sol[i-la+1]=1,n++;
    }
    fout<<n<<"\n";
    n=0;
    for(ull i=0;i<lb && n<1000;i++)
        if(sol[i]){
            fout<<i<<" ";
            n++;
        }
}

int main()
{
    citire();
    rabinkarp();
    return 0;
}