Cod sursa(job #2871554)

Utilizator darisavuSavu Daria darisavu Data 15 martie 2022 08:30:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long mod1=1e9+7,mod2=1e9+13,prim1=31,prim2=37;
string A,B;
unsigned long long p1=1,p2=1,hasha1,hasha2,hashb1,hashb2;
int sa,sb,nr,i;
vector<int>rez;
int main()
{
    f>>A>>B;
    sa=A.size();
    sb=B.size();
    if(sa>sb)
    {
        g<<"0";
        return 0;
    }
    //hash primul sir
    for(i=0;i<sa;i++)
    {
        hasha1=((hasha1*prim1)%mod1+A[i])%mod1;
        hasha2=((hasha2*prim2)%mod2+A[i])%mod2;
        if(i!=0)
        {
            p1=(p1*prim1)%mod1;
            p2=(p2*prim2)%mod2;
        }
    }
    //hash primele caractere din al doilea sir
     for(i=0;i<sa;i++)
    {
        hashb1=((hashb1*prim1)%mod1+B[i])%mod1;
        hashb2=((hashb2*prim2)%mod2+B[i])%mod2;
    }
    if(hasha1==hashb1&&hasha2==hashb2)
    {
        nr++;
        rez.push_back(0);
    }
    //hash restul sirului
    for(i=sa;i<sb;i++)
    {
        hashb1=((hashb1-((B[i-sa]*p1)%mod1)+mod1)*prim1%mod1+B[i])%mod1;
        hashb2=((hashb2-((B[i-sa]*p2)%mod2)+mod2)*prim2%mod2+B[i])%mod2;
        if(hashb1==hasha1&&hashb2==hasha2)
        {
            rez.push_back(i-sa+1);
            nr++;
        }
    }
    g<<nr<<'\n';
    for(i=0;i<nr;i++) g<<rez[i]<<" ";
    return 0;
}