Cod sursa(job #3184938)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 17 decembrie 2023 13:54:02
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include<fstream>
#include<string>
#include<vector>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
#define mod1 1000007
#define mod2 666013
std::vector<long long>ans;
std::string word;
std::string seq;
long long p=97, p2=53, nr=0;
long long seqKey1, localKey1, seqSize, V=1, V2=1;
long long seqKey2, localKey2;
void read()
{
    fin>>seq;
    fin>>word;
}

void preCalc()
{
    seqSize=seq.size();
    for(long long index=seqSize-1; index>=0; --index)
    {
        seqKey1=seqKey1%mod1+(seq[index]*V)%mod1;
        localKey1=localKey1%mod1+(word[index]*V)%mod1;

        seqKey2=seqKey2%mod2+(seq[index]*V2)%mod2;
        localKey2=localKey2%mod2+(word[index]*V2)%mod2;
        if(index>0)
        {
            V=(V*p)%mod1;
            V2=(V2*p2)%mod2;
        }
    }
}
void roll(char x, char erased)
{
    localKey1=(localKey1-(erased*V)%mod1)%mod1+mod1;//hash1
    localKey1=(localKey1*p+x)%mod1;

    localKey2=(localKey2-(erased*V2)%mod2)%mod2+mod2;//hash2
    localKey2=(localKey2*p2+x)%mod2;
}
void solve()
{
    if(localKey1==seqKey1 && localKey2==seqKey2)
    {
        ans.push_back(0);
        ++nr;
    }
    long long size=word.size();
    for(long long index=seqSize; index<size; ++index)
    {
        if(localKey1==seqKey1 && localKey2==seqKey2)
        {
            ans.push_back(index-seqSize);
            ++nr;
            if(nr==1000)
                break;
        }
        roll(word[index], word[index-seqSize]);
    }
    long long ansSize=ans.size();
    fout<<ansSize<<'\n';
    for(int index=0; index<ansSize; ++index)
        fout<<ans[index]<<' ';
}
int main()
{
    read();
    if(seq.size()>word.size())
    {
        fout<<"0\n";
        return 0;
    }
    preCalc();
    solve();
    return 0;
}