Cod sursa(job #3184941)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 17 decembrie 2023 14:08:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 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;
        }
    }
    fout<<nr<<'\n';
    for(int index=0; index<nr && index<1000; ++index)
        fout<<ans[index]<<' ';
}
int main()
{
    read();
    preCalc();
    solve();
    return 0;
}