Cod sursa(job #3184940)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 17 decembrie 2023 14:05:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include<fstream>
#include<string>
#include<vector>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
#define mod1 1000007
#define mod2 666013
#define p 97
std::vector<long long>ans;
std::string word;
std::string seq;
long long 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(int index=0; index<seqSize; ++index)
    {
        seqKey1=(seqKey1*p+seq[index])%mod1;
        seqKey2=(seqKey2*p+seq[index])%mod2;
        if(index)
        {
            V=(V*p)%mod1;
            V2=(V2*p)%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*p+x)%mod2;
}
void solve()
{
    if(seq.size()>word.size())
    {
        fout<<"0\n";
        return;
    }
    for(int index=0; index<seqSize; ++index)
    {
        localKey1=(localKey1*p+word[index])%mod1;
        localKey2=(localKey2*p+word[index])%mod2;
    }
    if(localKey1==seqKey1 && localKey2==seqKey2)
    {
        ans.push_back(0);
        ++nr;
    }
    long long size=word.size();


    for(long long index=seqSize; index<size; ++index)
    {
        roll(word[index], word[index-seqSize]);
        if(localKey1==seqKey1 && localKey2==seqKey2)
        {
            ans.push_back(index-seqSize+1);
            ++nr;
            if(nr==1000)
                break;
        }
    }
    long long ansSize=ans.size();
    fout<<ansSize<<'\n';
    for(int index=0; index<ansSize; ++index)
        fout<<ans[index]<<' ';
}
int main()
{
    read();
    preCalc();
    solve();
    return 0;
}