Cod sursa(job #3184958)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 17 decembrie 2023 14:43:45
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>
#include<string>
#include<vector>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
int p[2000010];
std::vector<int>ans;
std::string seq, word;
long long size,  nr=0;
void getPrefix()
{
    long long i=0, j=-1;
    p[0]=-1;
    while(i<size)
    {
        while(j>=0 && seq[i]!=seq[j])
            j=p[j];
        ++i;
        ++j;
        p[i]=j;
    }
}
void solve()
{
    long long size1=word.size();
    if(size>size1)
    {
        fout<<"0\n";
        return;
    }
    long long i=0, j=-1;
    while(i<size1)
    {
        while(j>=0 && word[i]!=seq[j])
            j=p[j];
        ++i;
        ++j;
        if(j==size)
        {
            ++nr;
            ans.push_back(i-size);
        }
    }
    fout<<nr<<'\n';
    for(int index=0; index<nr && index<1000; ++index)
        fout<<ans[index]<<' ';
}
int main()
{
    fin>>seq>>word;
    size=seq.size();
    getPrefix();
    solve();
    return 0;
}