Cod sursa(job #2739098)

Utilizator RTG123Razvan Diaconescu RTG123 Data 6 aprilie 2021 20:17:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int ln,lm,k,pi[2000001],rez[2000001],nr;
string n,m;
int main()
{
    f>>n>>m;
    ln=n.size();
    lm=m.size();
    //cout<<ln<<' '<<lm<<'\n';
    //pi[1]=0;
    n=n+'#'+m;
    k=0;
    for (int i=1; i<=lm+ln; i++)
    {
        k=pi[i-1];
        while (k>0 && n[k]!=n[i])
        {
            k=pi[k-1];
        }
        if (n[k]==n[i])
        {
            k++;
        }
        pi[i]=k;
       // cout<<i<<' '<<k<<'\n';
        //pi[i]=k;
        if (pi[i]==ln)
        {
            nr++;
            if (nr<=2000000)
            rez[nr]=i-2*ln;
        }
    }
    g<<nr<<'\n';
    for (int i=1; i<=nr; i++)
    {
        g<<rez[i]<<' ';
    }
    return 0;
}