Implementácia

Nakoniec si ešte ukážeme dve implementácie nášho algoritmu (obe v C++). Prvá z nich sa viac drží označení použitých v tomto texte. Druhá si niektoré veci pamätá trochu inak, ale je elegantnejšia.

Prvá implementácia:

vector<int> KMP(string text, string vzor)
{
    int n = text.size(), m = vzor.size();

    //hodnoty funkcie next. Hodnotu next[0] nepoužijeme.
    vector<int> next(m+1); 

    //Predrátanie funkcie next
    next[1] = 0;
    for(int j=2; j<=m; j++)
    {
        int k = next[j-1]+1;

        //Znižujeme premennú k až kým nenájdeme pasujúci prefix.
        //Mínus jednotky sú v indexoch, lebo číslujeme od nuly.
        while(vzor[k-1] != vzor[j-1]) 
        {
            if(k == 1)
            {
                k = 0;
                break;
            }
            k = next[k-1]+1;
        }
        next[j] = k;
    }

    //Hľadanie výskytu

    vector<int> vysledok; //sem si budeme ukladat pozicie vyskytov

    int zaciatok = 0; //začiatok overovanej časti textu (červená minca)
    int aktualny = 0; //znak textu, na ktorý sa ideme pozerať (modrá minca)
    while(aktualny < n && zaciatok < n)
    {
        int j = aktualny - zaciatok; //počet znakov vzoru, ktoré nám zatiaľ sedia
        if(text[aktualny] == vzor[j]) //znaky pasujú
        {
            aktualny++;
            if(aktualny - zaciatok == m) //nasli sme vyskyt
            {
                vysledok.push_back(zaciatok);
                zaciatok += m-next[m];
            }
        }
        else //znaky nepasujú
        {
            if(zaciatok == aktualny) //nefunguje ziaden zaciatok pred aktualnym znakom
            {
                zaciatok++;
                aktualny++;
            }
            else
            {
                zaciatok += j - next[j];
            }
        }
    }
    return vysledok;
}

Druhá implementácia

V tejto implemenácii si dodefinujeme $\mathrm{next}(0)$ ako $-1$, čo nám vyrieši zopár špeciálnych prípadov. Pri samotnom prechádzaní textu si potom nepamätáme začiatok výskytu ktorý kontrolujeme, ale písmeno textu na ktorom sme (premenná i) a počet znakov vzoru, ktoré zatiaľ sedia (premenná position, v predošlej implementácii v tejto úlohe vystupovalo j).

vector<int> KMP(string text, string pattern)
{
    vector<int> next(pattern.size()+1);

    //Compute next
    next[0] = -1;
    for(int i=0; i<pattern.size(); i++)
    {
        int back = next[i];
        while(back >= 0 && pattern[i] != pattern[back]) back = next[back];
        next[i+1] = back+1;
    }

    //Process the string
    vector<int> result;
    int position = 0;
    for(int i=0; i<text.size(); i++)
    {
        while(position >= 0 && text[i] != pattern[position]) position = next[position];
        position++;
        if(position == pattern.size())
        {
            result.push_back(i+1-pattern.size());
            position = next[position];
        }
    }
    return result;
}