11.3. Knuth-Morris-Pratt algoritmus

A Knuth-Morris-Pratt algoritmus bonyolultsága hasonlóan az előző algoritmushoz O(n + m). Ennél az algoritmusnál készítünk egy prefixtáblázatot, melyből leolvasható, hogy ha valamely karakter nem illeszkedik, mely eltolásokat hagyhatjuk ki mindenképp. A prefixtáblázat elkészítéséhez csak a mintára van szükség, és azt kell vizsgálnunk, hogy a minta prefixeinek (kezdőszeletei) valamely suffixe (végszelete) prefixe-e vagy sem. magyarul, előáll-e a minta eleje egy alakban, ahol , és esetleg üres karaktersorozat és = , vagy = . Ha igen, a prefixtáblázatba a leghosszabb , illetve hossza kerül be. A 3. ábrán sorra felsoroljuk a kezdőszeleteket, s alá- illetve föléhúzással jelöljük az egyező részeket. A knuth.htm állomány egy olyan programot tartalmaz, amely véletlen módon generált szövegre és mintára végrehajta a Knuth-Morris-Pratt módszert. A pontok jelzik a teljes szöveget, az aláhúzások az eltolásra utalnak, a zöld számok pedig az illeszkedést jelzik.

11.3. táblázat - 3. táblázat. Prefixfüggvény számítás


Function PREFIX-FÜGGVÉNY-SZÁMÍTÁS(P) 
Input: P minta 
Output: prefixfüggvény táblázata 
1  m = P.hossz 
2  p[1] = 0 
3  k = 0 
4  for q = 2 to m do 
5     while k ≥ 0 and P[k + 1] != P[q] do 
6        k = p[k]
7     endw 
8     if P[k + 1] == P[q] then 
9        k = k + 1
10    endif 
11    p[q] = k 
12 endfor 
13 return p

Procedure KMP-ILLESZTő(T,P) 
Input: T szöveg, P minta 
Eredmény: illeszkedés esetén figyelmeztetés 
1  n = T.hossz 
2  m = P.hossz 
3  p = PREFIX-FÜGGVÉNY-SZÁMÍTÁS(P) 
4  q = 0 
5  for i = 1 to n do 
6     while q ≥ 0 and P[q + 1] != T[i] do 
7        q = p[q]
8     endw 
9     if P[q + 1] == T[i] then 
10       q = q + 1 
11    endif
12    if q == m then 
13       kiír ( A minta előfordul q eltolással )
14       q = p[q] 
15    endif 
16 endfor