Cod sursa(job #2739073)

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