Cod sursa(job #2738823)

Utilizator AndiAndi39Sabo Andrei Claudiu AndiAndi39 Data 6 aprilie 2021 13:34:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include<iostream>
#include<fstream>
#include<cstring>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define nrm 2000005
char a[nrm],b[nrm];
int vlps[nrm],la,lb;
int rez[nrm];
int c=0;

void citire()
{
    fin>>a>>b;
    lb=strlen(b);
    la=strlen(a);
}

void afisare()
{
    fout<<c<<'\n';
    c=min(c,1000);
    for(int i=1;i<=c;i++)
    {
        fout<<rez[i]-la<<" ";
    }
}

void lps(char pat[])
{
    int i=0,j=1;
    while(j<la)
    {
        if(pat[i]==pat[j])
        {
            i++;
            vlps[j]=i;
            j++;
        }
        else
        {
            if(i!=0)
            {
                i=vlps[i-1];
            }
            else
            {
                vlps[j]=0;
                j++;
            }
        }
    }
}

void kmp()
{
    int ib=0,ia=0;
    while(ib<lb)
    {
        if(a[ia]==b[ib])
        {
            ia++;
            ib++;
        }
        if(ia==la)
        {
            c++;
            rez[c]=ib;
            ia=vlps[ia-1];
        }
        else
        {
            if(ib<lb && a[ia]!=b[ib])
            {
                if(ia!=0)
                {
                    ia=vlps[ia-1];
                }
                else
                {
                    ib++;
                }
            }
        }
    }
}

int main()
{
    citire();

    lps(a);

    kmp();

    afisare();

    fin.close();
    fout.close();
    return 0;
}