Knuth-Morris ja Pratt esittelevät lineaarisen aika-algoritmin merkkijonojen sovitusongelmalle. O:n (n) sovitusaika saavutetaan välttämällä vertailu 'S':n elementtiin, joka on aiemmin ollut mukana, verrattuna johonkin sovitettavaan kuvion 'p' elementtiin. toisin sanoen merkkijonoa 'S' ei koskaan tapahdu taaksepäin

KMP-algoritmin osat:

1. Etuliitetoiminto (Π): Kuvion etuliitefunktio Π kiteyttää tiedon siitä, kuinka kuvio vastaa itsensä muutosta. Tätä tietoa voidaan käyttää välttämään kuvion 'p' turha siirtyminen. Toisin sanoen tämä mahdollistaa merkkijonon 'S.'

2. KMP-ottelut: Kun syötteinä on merkkijono 'S', kuvio 'p' ja etuliitefunktio 'Π', etsi 'p':n esiintyminen 'S':ssä ja palauttaa 'p':n siirtymien lukumäärän, jonka jälkeen esiintymiä löydetään.

Etuliitefunktio (Π)

Laske pseudokoodin jälkeen etuliitefunktio Π:

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

Ajoaika-analyysi:

Yllä olevassa pseudokoodissa etuliitefunktion laskemiseksi for-silmukka vaiheesta 4 vaiheeseen 10 kulkee 'm' kertaa. Vaiheet 1–3 vievät vakioajan. Tästä syystä etuliitefunktion laskenta-aika on O (m).

Esimerkki: Laske Π alla olevalle kuviolle 'p':

muuntaa int merkkijonoksi java

Ratkaisu:

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

6-kertaisen iteroinnin jälkeen etuliitefunktion laskenta on valmis:

KMP ottelut:

KMP-sovitin, jonka syötteenä on kaava 'p', merkkijono 'S' ja etuliitefunktio 'Π', löytää vastaavuuden p:stä S:ssä. Laske KMP-algoritmin vastaava komponentti seuraavan pseudokoodin avulla:

 <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 

Ajoaika-analyysi:

Vaiheesta 5 alkava for-silmukka suoritetaan 'n' kertaa, eli niin kauan kuin merkkijonon pituus 'S'. Koska vaiheet 1 - 4 vievät vakioaikoja, tämä hallitsee ajoaikaa silmukalle. Täten sovitusfunktion ajoaika on O (n).

Esimerkki: Merkkijono 'T' ja kuvio 'P' seuraavasti:

Suoritetaan KMP-algoritmi selvittääksemme, esiintyykö 'P':ssä 'T'.

'p':n etuliitefunktiolle, ? on laskettu aiemmin ja on seuraava:

Ratkaisu:

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

Kuvion 'P' on havaittu olevan monimutkainen merkkijonossa 'T'. Vuorojen kokonaismäärä, joka tapahtui, jotta osuma löytyi, on i-m = 13 - 7 = 6 vuoroa.