Cod sursa(job #3184955)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 17 decembrie 2023 14:38:45
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include<fstream>
#include<string>
#include<vector>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
int p[2000001];
std::vector<int>ans;
std::string seq, word;
long long size,  nr;
void getPrefix()
{
    int 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();
    int 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;
}