KMP

RNO-Wiki

Spis treści

1 Problem wyszukiwania wzorca (WW)
2 Automaty skończone
3 Funkcja prefiksowa Knutha
4 Algorytm Knutha-Morrisa-Pratta
5 Linki

Problem wyszukiwania wzorca (WW)

Mamy dane słowo T i wzorzec P. Nasze zadanie polega na tym, żeby znaleźć wszystkie pozycje występowania wzorca P w tekście P. Przy czym mówimy, że wzorzec P występuje na i-tej pozycji, wtedy i tylko wtedy, gdy począwszy od i-tej pozycji, wzorzec "pasuje" do tekstu.

Automaty skończone

Wyszukiwanie wzorca w tekście można realizować za pomocą pewnych automatów skończonych. Oto przykład automatu rozpoznającego w tekscie wzorzec "abaaba" :

Funkcja prefiksowa Knutha

Dla słowa P[0..(m-1)] definiujemy funkcję prefiksową Knutha następująco:

 pi[0] = 0
 pi[k] = długość najdłuższego prefiksu słowa P[0..(k-1)] będącego sufiksem słowa P[1..(k)],  k=1,...,n-1

int   m, k, q, pi[1000001];
char  P[1000001]; // P[] - wzorzec o dlugosci m
 
void CPF() // obliczanie funkcji prefiksowej Knutha
{
        // m = strlen(P);
        pi[0] = 0; q = 0;
        for(k=1; k<m; k++)
        {
                //niezmiennik: q=pi[k-1]
                while(q>0 && P[k] != P[q])
                        q=pi[q-1];
                if(P[k] == P[q])
                        pi[k] = ++q;
                else
                        pi[k] = 0;
        }
}

Algorytm Knutha-Morrisa-Pratta

Generalnie idea algorytmu jest bardzo prosta. Niech n oznacza długość tekstu T, a m - długość wzorca P. Problem WW można bardzo prosto rozwiązać sprawdzając dla każdego i, czy kolejne m pozycji się zgadza. Takie sprawdzanie jest jednak bardzo nieefektywne, gdyż dla pesymistycznego przypadku wychodzi nam złożoność rzędu <math>n^2</math>. Taki algorytm nazywany jest algorytmem N ("naiwny"). Można, jednak, taki sam pomysł napisać tak, aby działał liniowo. Zauważmy, że nie trzeba za każdym razem "przesuwać się" w tekście T o jedną pozycję. Czasami możemy zrobić duży skok. To zdecydowanie polepsza złożoność algorytmu. Załóżmy, że mamy policzoną tablicę pi. Dzięki temu wiemy, że gdy na pozycji j występuje niezgodność wzorca z tekstem, możemy j ustawić na pi[j] (dlatego, że na pewno pi[j] pierwszych liter wzorca zgadza się z pi[j] ostatnich liter wzorca) i sprawdzać dalej, pomijając trochę liter.

Poniższy program rozwiązuje zadanie [1]

#include <cstdio>
#include <string>
 
using namespace std;
 
int   n, m, k, q, pi[1000001];
char  P[1000001]; // P[] - wzorzec o dlugosci m
char  T[1000001]; // T[] - tekst o dlugosci n
 
void CPF() // obliczanie funkcji prefiksowej Knutha
{
//  tak samo, jak powyżej
}
 
void kmp()
{
    int q=0;
    //  n = strlen(s);
    for(int i=0; i<n; i++)
    {
        while(q>0 && T[i] != P[q]) q = pi[q-1];
        if (T[i] == P[q]) q++;
        if(q == m)
        {
            // znaleziono wzorzec !!!
            printf("%d\n", i-m + 1); // plus jeden
            q = pi[q-1];
        }
    }
}
 
int main()
{
    int Test;
    scanf("%d\n", &Test); //Test - liczba przypadków testowych.
    while(Test--)
    {
        scanf("%d\n", &m);
        scanf("%s", P); // m = strlen(P);
//      scanf("%d\n", &n);
        scanf("%s", T); n = strlen(T);
        CPF();
        if(m <= n) kmp();
    }
    return 0;
}