Knuth-Morris i Pratt wprowadzają liniowy algorytm czasu dla problemu dopasowania ciągów. Czas dopasowania O (n) osiąga się poprzez unikanie porównania z elementem „S”, który był wcześniej zaangażowany w porównaniu z pewnym elementem wzorca „p”, który ma zostać dopasowany. tj. cofanie się na ciągu „S” nigdy nie następuje

Składniki algorytmu KMP:

1. Funkcja przedrostka (Π): Funkcja przedrostka Π dla wzorca zawiera wiedzę o tym, jak wzór dopasowuje się do samego przesunięcia. Informacje te można wykorzystać, aby uniknąć bezużytecznego przesunięcia wzorca „p”. Innymi słowy, pozwala to uniknąć cofania się łańcucha „S”.

2. Mecze KMP: Mając ciąg „S”, wzór „p” i funkcję przedrostka „Π” jako dane wejściowe, znajdź wystąpienie „p” w „S” i zwróć liczbę przesunięć „p”, po których zostaną znalezione wystąpienia.

Funkcja przedrostka (Π)

Poniższy pseudokod oblicza funkcję przedrostka Π:

 <strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m &#x2190;length [P] //&apos;p&apos; pattern to be matched 2. &#x3A0; [1] &#x2190; 0 3. k &#x2190; 0 4. for q &#x2190; 2 to m 5. do while k &gt; 0 and P [k + 1] &#x2260; P [q] 6. do k &#x2190; &#x3A0; [k] 7. If P [k + 1] = P [q] 8. then k&#x2190; k + 1 9. &#x3A0; [q] &#x2190; k 10. Return &#x3A0; 

Analiza czasu pracy:

W powyższym pseudokodzie służącym do obliczania funkcji przedrostka pętla for od kroku 4 do kroku 10 jest wykonywana „m” razy. Kroki od 1 do 3 zajmują stały czas. Zatem czas działania funkcji przedrostkowej wynosi O (m).

Przykład: Oblicz Π dla poniższego wzoru „p”:

dlaczego ciąg niezmienny w Javie

Rozwiązanie:

 Initially: m = length [p] = 7 Π [1] = 0 k = 0 

Po 6 iteracjach obliczenia funkcji przedrostkowej są zakończone:

Mecze KMP:

Dopasowujący KMP ze wzorcem „p”, ciągiem „S” i funkcją przedrostka „Π” jako danymi wejściowymi, znajduje dopasowanie p w S. Poniższy pseudokod oblicza pasujący komponent algorytmu KMP:

 <strong>KMP-MATCHER (T, P)</strong> 1. n &#x2190; length [T] 2. m &#x2190; length [P] 3. &#x3A0;&#x2190; COMPUTE-PREFIX-FUNCTION (P) 4. q &#x2190; 0 // numbers of characters matched 5. for i &#x2190; 1 to n // scan S from left to right 6. do while q &gt; 0 and P [q + 1] &#x2260; T [i] 7. do q &#x2190; &#x3A0; [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q &#x2190; q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print &apos;Pattern occurs with shift&apos; i - m 12. q &#x2190; &#x3A0; [q] // look for the next match 

Analiza czasu pracy:

Pętla for rozpoczynająca się w kroku 5 jest wykonywana n razy, tj. tak długo, jak długość łańcucha „S”. Ponieważ kroki 1 do 4 mają stałe czasy, czas działania pętli jest zdominowany przez ten czas. Zatem czas działania funkcji dopasowującej wynosi O (n).

Przykład: Biorąc pod uwagę ciąg „T” i wzór „P” w następujący sposób:

Wykonajmy algorytm KMP, aby sprawdzić, czy „P” występuje w „T”.

Dla „p” funkcja przedrostka? została obliczona wcześniej i wygląda następująco:

Rozwiązanie:

 Initially: n = size of T = 15 m = size of P = 7 

Stwierdzono, że wzorzec „P” wykazuje złożoność w ciągu znaków „T”. Całkowita liczba przesunięć, które miały miejsce, aby znaleźć dopasowanie, wynosi i-m = 13 - 7 = 6 przesunięć.