Knuth-Morris i Pratt uvode linearni vremenski algoritam za problem sparivanja nizova. Vrijeme podudaranja O (n) postiže se izbjegavanjem usporedbe s elementom 'S' koji je prethodno bio uključen u usporedbu s nekim elementom uzorka 'p' koji treba uskladiti. tj. povratno praćenje na nizu 'S' nikada se ne događa

Komponente KMP algoritma:

1. Funkcija prefiksa (Π): Funkcija prefiksa, Π za uzorak, sažima znanje o tome kako se uzorak podudara s pomakom samog sebe. Ove se informacije mogu koristiti za izbjegavanje beskorisnog pomicanja uzorka 'p'. Drugim riječima, ovo omogućuje izbjegavanje povratnog praćenja niza 'S'.

2. KMP utakmice: S nizom 'S', uzorkom 'p' i funkcijom prefiksa 'Π' kao ulazima, pronađite pojavljivanje 'p' u 'S' i vraća broj pomaka 'p' nakon kojih su pronađena pojavljivanja.

Funkcija prefiksa (Π)

Sljedeći pseudo kod izračunava funkciju prefiksa, Π:

 <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 vremena trajanja:

U gornjem pseudo kodu za izračun funkcije prefiksa, for petlja od koraka 4 do koraka 10 izvodi se 'm' puta. Od koraka 1 do koraka 3 potrebno je konstantno vrijeme. Stoga je vrijeme rada funkcije prefiksa računanja O (m).

Primjer: Izračunajte Π za uzorak 'p' u nastavku:

pozivanje js funkcije iz html-a

Riješenje:

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

Nakon iteracije 6 puta, izračun funkcije prefiksa je dovršen:

KMP odgovara:

KMP Macher s uzorkom 'p', nizom 'S' i funkcijom prefiksa 'Π' kao ulazom, pronalazi podudaranje p u S. Sljedeći pseudo kod izračunava komponentu podudaranja KMP algoritma:

 <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 vremena trajanja:

Petlja for koja počinje u koraku 5 izvodi se 'n' puta, tj. koliko je duljina niza 'S'. Budući da su od koraka 1 do koraka 4 potrebna konstantna vremena, vrijeme izvođenja dominira ovo za petlju. Stoga je vrijeme rada funkcije podudaranja O (n).

Primjer: Dat je niz 'T' i uzorak 'P' kako slijedi:

Izvršimo KMP algoritam da utvrdimo pojavljuje li se 'P' u 'T'.

Za 'p' funkcija prefiksa, ? je prethodno izračunat i iznosi kako slijedi:

Riješenje:

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

Utvrđeno je da se složenost uzorka 'P' pojavljuje u nizu 'T'. Ukupan broj promjena koje su se dogodile da bi se pronašlo podudaranje je i-m = 13 - 7 = 6 promjena.