Cod sursa(job #2871563)

Utilizator darisavuSavu Daria darisavu Data 15 martie 2022 08:42:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <string>
#define mod1 1000000007
#define mod2 1000000013
#define prim1 31
#define prim2 37
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
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=((prim1*(hashb1-((B[i-sa]*p1)%mod1)+mod1))%mod1+B[i])%mod1;
        hashb2=((prim2*(hashb2-((B[i-sa]*p2)%mod2)+mod2))%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<1000;i++) g<<rez[i]<<" ";
    return 0;
}