Cod sursa(job #2104206)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 11 ianuarie 2018 13:29:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<string>

using namespace std;

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

const int NMax=2000005;
int Poz[NMax],N,M,Sol[1003],Dim=0;
string Pattern,Text;

void PreKMP()
{
    int K=0;
    for(int i=2;i<N;i++)
    {
        while(K && Pattern[i]!=Pattern[K+1])
            K=Poz[K];
        if(Pattern[i]==Pattern[K+1])
            K++;
        Poz[i]=K;
    }
}

void KMP()
{
    PreKMP();
    int K=0;
     for(int i=1;i<M;i++)
    {
        while(K && Text[i]!=Pattern[K+1])
            K=Poz[K];
        if(Text[i]==Pattern[K+1])
            K++;
        if(K==N-1)
        {
            K=Poz[K];
            Dim++;
            if(Dim<=1000)
                Sol[Dim]=i-N+1;
        }
    }

}

int main()
{
    fin>>Pattern>>Text;
    Pattern=' '+Pattern;
    Text=' '+Text;
    N=Pattern.size();
    M=Text.size();
    KMP();
    fout<<Dim<<'\n';
    Dim=min(Dim,1000);
    for(int i=1;i<=Dim;i++)
        fout<<Sol[i]<<" ";
}