Knuth-Morris a Pratt zavádějí lineární časový algoritmus pro problém porovnávání řetězců. Času porovnávání O (n) je dosaženo tím, že se vyhneme porovnávání s prvkem „S“, který byl dříve zapojen do srovnání s některým prvkem vzoru „p“, který má být porovnáván. tj. zpětné sledování řetězce 'S' nikdy nenastane

Komponenty algoritmu KMP:

1. Funkce předpony (Π): Funkce předpony, Π pro vzor zapouzdřuje znalosti o tom, jak se vzor shoduje s jeho posunem. Tato informace může být použita, aby se zabránilo zbytečnému posunu vzoru 'p.' Jinými slovy to umožňuje vyhnout se zpětnému sledování řetězce 'S.'

2. Zápasy KMP: S řetězcem 'S', vzorem 'p' a prefixovou funkcí 'Π' jako vstupy najděte výskyt 'p' v 'S' a vrátí počet posunů 'p', po kterých jsou nalezeny výskyty.

Funkce předpony (Π)

Následující pseudokód vypočítá funkci prefixu, Π:

 <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; 

Analýza doby běhu:

Ve výše uvedeném pseudokódu pro výpočet funkce předpony se smyčka for od kroku 4 do kroku 10 spustí 'm' krát. Kroky 1 až 3 zabírají konstantní čas. Doba běhu výpočetní prefixové funkce je tedy O (m).

Příklad: Vypočítejte Π pro vzor 'p' níže:

Fibonacciho kód java

Řešení:

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

Po šestinásobné iteraci je výpočet funkce prefixu dokončen:

KMP se shoduje:

KMP Matcher se vzorem 'p', řetězcem 'S' a prefixovou funkcí 'Π' jako vstupem najde shodu p v S. Následující pseudokód vypočítá odpovídající komponentu KMP algoritmu:

 <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 

Analýza doby běhu:

Smyčka for začínající v kroku 5 běží „n“ krát, tj. tak dlouho, jak je délka řetězce „S“. Protože kroky 1 až 4 trvají konstantní časy, převládá doba běhu pro smyčku. Doba běhu porovnávací funkce je tedy O (n).

Příklad: Daný řetězec „T“ a vzor „P“ takto:

Spusťte KMP Algoritmus, abychom zjistili, zda se 'P' vyskytuje v 'T.'

Pro 'p' funkci předpony, ? byl vypočten dříve a je následující:

Řešení:

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

U vzoru 'P' bylo zjištěno, že složitost se vyskytuje v řetězci 'T.' Celkový počet směn, které proběhly k nalezení shody, je i-m = 13 - 7 = 6 směn.