Knuth-Morris in Pratt uvedeta linearni časovni algoritem za problem ujemanja nizov. Čas ujemanja O (n) se doseže z izogibanjem primerjavi z elementom 'S', ki je bil predhodno vključen v primerjavo z nekim elementom vzorca 'p', ki ga je treba ujemati. t.j. povratno sledenje na nizu 'S' se nikoli ne pojavi

Komponente algoritma KMP:

1. Funkcija predpone (Π): Funkcija predpone, Π za vzorec, zajema znanje o tem, kako se vzorec ujema s premikom samega sebe. Te informacije se lahko uporabijo za izogibanje neuporabnemu premikanju vzorca 'p'. Z drugimi besedami, to omogoča izogibanje povratnemu sledenju niza 'S'.

2. Tekme KMP: Z nizom 'S', vzorcem 'p' in funkcijo predpone 'Π' kot vhodi poiščite pojavitev 'p' v 'S' in vrne število premikov 'p', po katerih so najdene pojavitve.

Funkcija predpone (Π)

Naslednja psevdo koda izračuna funkcijo predpone, Π:

 <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 časa delovanja:

V zgornji psevdo kodi za izračun funkcije predpone se zanka for od koraka 4 do koraka 10 izvede 'm'-krat. Koraki od 1 do 3 zahtevajo konstanten čas. Zato je čas delovanja računalniške funkcije predpone O (m).

primer: Izračunajte Π za vzorec 'p' spodaj:

orodna vrstica za hitri dostop ms word

rešitev:

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

Po 6-kratni ponovitvi je izračun funkcije predpone končan:

KMP se ujema z:

Ujemanje KMP z vzorcem 'p', nizom 'S' in funkcijo predpone 'Π' kot vhodom najde ujemanje p v S. Naslednja psevdo koda izračuna komponento ujemanja algoritma 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 časa delovanja:

Zanka for, ki se začne v koraku 5, se izvede 'n'-krat, tj. dokler je dolžina niza 'S'. Ker koraki od 1 do 4 zahtevajo konstantne čase, čas delovanja prevladuje za zanko. Tako je čas delovanja funkcije ujemanja O (n).

primer: Podan je niz 'T' in vzorec 'P', kot sledi:

Izvedimo algoritem KMP, da ugotovimo, ali se 'P' pojavi v 'T'.

Za 'p' funkcijo predpone, ? je bil predhodno izračunan in je naslednji:

rešitev:

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

Ugotovljeno je bilo, da se kompleksnost vzorca 'P' pojavlja v nizu 'T'. Skupno število premikov, ki so se zgodili za iskanje ujemanja, je i-m = 13 - 7 = 6 premikov.