Algorytm KMP

Rafał Nowak

Wprowadzenie

Rozważmy problem wyszukiwania wzorca w tekście opisany w artykule Wyszukiwanie wzorca.
W artykule tym przedstawimy algorytm KMP, który będzie znacznie szybszy od opisanego wcześniej algorytmu.
naiwnego. Mianowicie, będzie dział w czasie liniowym. Do tego celu wprowadzimy kilka dodatkowych pojęć.

Powiemy, że słowo $u[1..k]$ jest prefiksem słowa $w[1..l]$, jeśli

(1)

\begin{align} u[1+j] = w[1+j] \quad \text{dla}\quad j=0,1,\ldots,k-1 \end{align}

tzn. słowo $w$ zaczyna się słowem $u$, np. jest tak dla $u$=ABCAA, $w$=ABCAABBAABAABAAB.

Powiemy, że słowo $u[1..k]$ jest sufiksem słowa $w[1..l]$, jeśli

(2)

\begin{align} u[1+j] = w[l-k+1+j] \quad \text{dla}\quad j=0,1,\ldots,k-1 \end{align}

tzn. słowo $w$ kończy się słowem $u$, np. jest tak dla $u$=ABAAB, $w$=ABCAABBAABAABAAB.

Wreszcie powiemy, że słowo $u[1..k]$ jest prefikso-sufiksem słowa $w[1..l]$, jeśli
słowo $u$ jest zarówno jego prefiksem i sufiksem. Na przykład słowo $u$=AB jest prefikso-sufiksem słowa $w$=ABCAABBAABAABAAB.

Okazuje się, że przy wyszukiwaniu wzorca w tekście, bardzo przydatna jest znajomość najdłuższego prefikso-sufiksu całego wzorca i nie tylko. Oczywiście, każde słowo jest swoim prefiksem i sufiksem, zatem jest również prefikso-sufiksem. Dalej będą nas jednak interesowały właściwe prefikso-sufuksy, tj. takie, które nie są całym słowem.
Dalej będziemy naywali je po prostu ramkami. Na przykład, najdłuższą ramką słowa

jest słowo ABA. Oczywiście istnieje również druga ramka — słowo A, ale jest ona krótsza. W następnym rozdziale pokażemy jak obliczać długość najdłuższej ramki dla każdego prefiksu wzorca w tekście.

Przykład
Rozważmy słowo ABAABAAABAAB. Na poniższym rysunku zaznaczono dwie jego ramki

Idea algorytmu KMP

Znając najdłuższą ramkę naszego wzorca, możemy bardzo przyspieszyć działanie algorytmu naiwnego.
Wyobraźmy sobie sytuację, w której udało nam się znaleźć wzorzec $P$ na pozycji $i$ w tekście. Chcąc teraz kontynuować wyszukiwanie, zastanawiamy się, gdzie skoczyć ze wskaźnikiem $i$. Algorytm naiwny zwiększał $i$ po prostu o jeden. Jeśli jednak znamy długość najdłużej ramki naszego wzorca, to natychmiast wiadomo gdzie jest potencjalne następne miejsce, na którym mógłby występować wzorzec; zob. poniższy rysunek

Ten pomysł można oczywiście stosować, nie tylko, gdy znajdziemy występowanie wzorca, ale również, gdy nie uda nam się go znaleźć. Wystarczy na powyższym obrazku wyobrazić, sobie, że $P$ jest prefiksem wzorca.
I tutaj właśnie przydaje się znajomość najdłużej ramki każdego prefiksu wzorca. Przejdźmy więc do następnego rozdziału.

Tablica prefikso-sufiksowa

Naszym celem jest wyznaczenie długości najdłuższej ramki dla każdego prefiksu wzorca $P$.
Na przykład dla słowa ABAABAAABAAB, jego kolejne prefiksy to:

A
AB
ABA
ABAA
ABAAB
ABAABA
ABAABAA
ABAABAAA
ABAABAAAB
ABAABAAABA
ABAABAAABAA
ABAABAAABAAB

a ich najdłuższe ramki mają długość odpowiednio:

$j$ (długość prefiksu)	Prefiks	Najdłuższa ramka prefiksu	$\pi[j]$ (długość ramki)
1	A	brak	0
2	AB	brak	0
3	ABA	A	1
4	ABAA	A	1
5	ABAAB	AB	2
6	ABAABA	ABA	3
7	ABAABAA	ABAA	4
8	ABAABAAA	A	1
9	ABAABAAAB	AB	2
10	ABAABAAABA	ABA	3
11	ABAABAAABAA	ABAA	4
12	ABAABAAABAAB	ABAAB	5

Obliczanie tablicy

Przejdźmy więc do opisu metody obliczania tablicy $\pi[1..m]$ — tablicy długości najdłuższych właściwych prefikso-sufiksów dla wzorca $P[1..m]$.
Po pierwsze tablicę obliczamy dla kolejnych wartości $j=1,2,\ldots,m$.

Oczywiście, zaczynamy od wartości

(3)

\begin{align} \pi[1] = 0, \end{align}

gdyż słowo jednoliterowe nie posiada żadnej ramki. Można myśleć, że posiada ramkę będącą słowem pustym o długości 0.
Następnie przypuśćmy, że mamy już obliczone wartości $\pi[1], \pi[2], \ldots, \pi[j-1]$ i chcemy obliczyć $\pi[j]$.
Oznaczmy $t = \pi[j-1]$, tzn. niech $t$ oznacza długość poprzedniej ramki. Zauważmy, że

(4)

\begin{align} \text{jeśli } P[t+1]=P[j], \text{ to } \pi[j] = t+1 \end{align}

Innymi słowy, jeśli nowa litera $P[j]$ przedłuża poprzednią ramkę (o długości $t=\pi[j-1]$), to natychmiast otrzymujemy najdłuższą ramkę dla prefiksu $j$ literowego. Dzieje się tak na przykład dla podanego wcześniej słowa $P$ i dla $j=3,5,6,7,9,10,11,12$. Jeśli zaś tak nie jest, tzn. zachodzi $P[t+1]\neq P[j]$, to okazuje się, że wystarczy popatrzeć na najdłuższą ramkę poprzedniej ramki, a więc spróbować przedłużyć ramkę o długości $\pi[t]$. Dowód tego faktu pozostawiamy czytelnikowi.
W ten sposób możemy już zapisać w pseudo-języku algorytm obliczania tablicy prefikso-sufiksowej $\pi[1..m]$.
Uwaga: do wygodnego zapisu algorytmu, wprowadzić pomocniczą wartość $\pi[0]=-1$.

pi[0] := -1
t := -1
for j from 1 to m do   //  niezmiennik : t = pi[j-1]
  while t≥0 and P[t+1]≠P[j] do
    t := pi[t]
  end
  t := t+1
  pi[j] := t
end

Algorytm Morrisa-Pratta

Obliczona wcześniej funkcja $\pi$ nazywana jest w literaturze funkcją Knutha-Morrisa-Prata. Poniższy algorytm, korzysta z tej tablicy dość istotnie i nazywa się algorytmem Morrisa-Pratta.
Poniższy algorytm wypisuje wszystkie pozycje, na których występuje wzorzec $P[1..m]$ w tekście $T[1..n]$. Algorytm korzysta z obliczonej wcześniej tablicy $\pi[1..m]$.

i := 0; j := 0
while i≤n-m do
  while j<m and P[j+1]=T[i+j+1] do
    j := j+1
  end
  if j=m then wypisz i
  i := i+j-pi[j]
  j := max(0, pi[j])
end

Analiza algorytmu

Powyższy algorytm ma wiele wspólnego z algorytmem naiwnym.
Pierwsza pętla while po przechodzi ze wskaźnikiem i aż do ostatniej pozycji, na której mógłby znajdować się wzorzec $P$. Tym razem zmienna i nie zwiększa się zawsze o jeden. Wewnętrzna pętla while sprawdza naiwnie jak dużo liter wzorca pasuje na pozycji i. Widzimy więc, że po znalezieniu prefiksu j literowego zmienna i zwiększa się o j-pi[j]. Ponieważ pi[j] jest długością najdłużej ramki tego prefiksu, więc pozycja i+j-pi[j] jest pierwszą pozycją, na której mogłoby pojawić się kolejne wystąpienie wzorca. Warto również podkreślić to, że zmienna j nie jest zerowana. Wręcz przeciwnie, za pomocą pi[j] szybko uzyskujemy liczbę liter zgodnych z pewnym prefiksem wzorca. Przy następnej pozycji i nie będziemy musieli więc ich sprawdzać. Dowód poprawności tego wynika natychmiast z definicji funkcji prefiksowej $\pi[1..m]$.

Złożoność czasowa
Na pierwszy rzut oka widzimy dwie pętle, które mogłyby sugerować złożoność czasową $\mathcal{O}(n\cdot m)$.
Jednak tutaj, mamy taką sytuację, że $\pi[j] < j$ dla każdego $j=0,1,\ldots,m$. W związku z tym, można wykazać, że w każdym kroku obu pętli rośnie wartość sumy $i+j$. Ponieważ $i\leq n-m$ i $j\leq m$ więc suma ta jest ograniczona przez $n$. Stąd otrzymujemy, że złożoność algorytmu Morrisa-Pratta jest liniowa, wynosi $\mathcal{O}(n)$.