Knuth-Morris ir Pratt pristato linijinį laiko algoritmą eilučių atitikimo problemai spręsti. O (n) atitikimo laikas pasiekiamas vengiant lyginimo su „S“ elementu, kuris anksčiau buvo įtrauktas, lyginant su kokiu nors suderintinu modelio „p“ elementu. y., eilute „S“ neatsitraukiama niekada

KMP algoritmo komponentai:

1. Priešdėlio funkcija (Π): Modelio priešdėlio funkcija Π apima žinias apie tai, kaip modelis atitinka jo paties poslinkį. Šią informaciją galima naudoti siekiant išvengti nenaudingo modelio „p“ poslinkio. Kitaip tariant, tai leidžia išvengti eilutės „S“ grįžimo atgal.

2. KMP rungtynės: Įvesdami eilutę „S“, šabloną „p“ ir priešdėlio funkciją „Π“, raskite „p“ įvykį „S“ ir grąžina „p“ poslinkių, po kurių randami įvykiai, skaičių.

Priešdėlio funkcija (Π)

Po pseudo kodo apskaičiuokite priešdėlio funkciją, Π:

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

Veikimo laiko analizė:

Aukščiau pateiktame pseudo kode, skirtame priešdėlio funkcijai apskaičiuoti, ciklas for nuo 4 veiksmo iki 10 veiksmo paleidžiamas „m“ kartų. Nuo 1 iki 3 žingsnių reikia pastovaus laiko. Taigi priešdėlio funkcijos skaičiavimo laikas yra O (m).

Pavyzdys: Apskaičiuokite Π žemiau esančiam modeliui „p“:

Atsisiųsti xvideoservicethief ubuntu 14.04

Sprendimas:

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

Pakartojus 6 kartus, priešdėlio funkcijos skaičiavimas baigtas:

KMP rungtynės:

KMP atitikmuo su šablonu „p“, eilute „S“ ir priešdėlio funkcija „Π“ kaip įvestis, suranda p atitiktį S. Po pseudokodo apskaičiuokite atitinkantį KMP algoritmo komponentą:

 <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 

Veikimo laiko analizė:

Ciklas for, prasidedantis 5 žingsniu, paleidžiamas „n“ kartų, t. y. tol, kol eilutės ilgis yra „S“. Kadangi nuo 1 iki 4 veiksmo laikas yra pastovus, ciklo veikimo laikas dominuoja. Taigi atitikimo funkcijos veikimo laikas yra O (n).

Pavyzdys: Pateikiama eilutė „T“ ir raštas „P“ taip:

Vykdykime KMP algoritmą, kad sužinotume, ar „P“ yra „T“.

„p“ priešdėlio funkcijai, ? buvo apskaičiuotas anksčiau ir yra toks:

Sprendimas:

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

Nustatyta, kad šablonas „P“ yra sudėtingas eilutėje „T“. Bendras pamainų skaičius, kuris įvyko, kad būtų galima rasti atitiktį, yra i-m = 13 - 7 = 6 pamainos.