Cod sursa(job #2978934)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 14 februarie 2023 17:27:05
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
const int mod1=999997;
const int mod2=1000003;
int ha1,ha2,nr,hb1,hb2;
vector<int>sol;
int main()
{
    f>>a>>b;
    int p1,p2,p;
    p1=p2=1;
    p=73;
    if(a.size()>b.size())
    {
        g<<0;
        return 0;
    }
    for(int i=0;i<a.size();i++)
    {
        ha1=(ha1*p+(a[i]-'A'+1))%mod1;
        ha2=(ha2*p+(a[i]-'A'+1))%mod2;

        hb1=(hb1*p+(b[i]-'A'+1))%mod1;
        hb2=(hb2*p+(b[i]-'A'+1))%mod2;
        if(i)
        {
            p1=(p*p1)%mod1;
            p2=(p*p2)%mod2;
        }
    }
    if(ha1==hb1&&ha2==hb2)
        sol.push_back(0),nr++;
    for(int i=a.size();i<b.size();i++)
    {
        int last=(b[i-a.size()]-'A'+1);
        int next=b[i]-'A'+1;
        hb1=((hb1-(last*p1)%mod1+mod1)*p+next)%mod1;
        hb2=((hb2-(last*p2)%mod2+mod2)*p+next)%mod2;
        if(ha1==hb1&&ha2==hb2)
            sol.push_back(i-a.size()+1),nr++;
    }
    g<<nr<<'\n';
    for(auto x : sol)
        g<<x<<" ";
    return 0;
}