Knuth-Morris og Pratt introduserer en lineær tidsalgoritme for strengtilpasningsproblemet. En matchingstid på O (n) oppnås ved å unngå sammenligning med et element av 'S' som tidligere har vært involvert i sammenligning med et element i mønsteret 'p' som skal matches. dvs. tilbakesporing på strengen 'S' forekommer aldri

Komponenter i KMP-algoritmen:

1. Prefiksfunksjonen (Π): Prefiksfunksjonen, Π for et mønster innkapsler kunnskap om hvordan mønsteret samsvarer med skiftet av seg selv. Denne informasjonen kan brukes til å unngå en ubrukelig forskyvning av mønsteret 's.' Med andre ord, dette gjør det mulig å unngå tilbakesporing av strengen 'S.'

2. KMP-treffene: Med streng 'S', mønster 'p' og prefiksfunksjon 'Π' som innganger, finn forekomsten av 'p' i 'S' og returnerer antall skift av 'p' hvoretter forekomster er funnet.

Prefiksfunksjonen (Π)

Følgende pseudokode beregner prefiksfunksjonen, Π:

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

Kjøretidsanalyse:

I pseudokoden ovenfor for å beregne prefiksfunksjonen, kjører for-løkken fra trinn 4 til trinn 10 'm' ganger. Trinn 1 til trinn 3 tar konstant tid. Derfor er driftstiden for beregningsprefiksfunksjonen O (m).

Eksempel: Beregn Π for mønsteret 'p' nedenfor:

pseudokode java

Løsning:

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

Etter iterasjon 6 ganger er prefiksfunksjonsberegningen fullført:

KMP-kampene:

KMP Matcher med mønsteret 'p', strengen 'S' og prefiksfunksjonen 'Π' som input, finner en match av p i S. Følgende pseudokode beregner samsvarskomponenten til KMP-algoritmen:

 <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 

Kjøretidsanalyse:

For-løkken som begynner i trinn 5, kjører 'n' ganger, dvs. så lang som lengden på strengen 'S.' Siden trinn 1 til trinn 4 tar konstante tider, domineres kjøretiden av dette for sløyfen. Driftstiden for matchingsfunksjonen er derfor O (n).

Eksempel: Gitt en streng 'T' og mønster 'P' som følger:

La oss kjøre KMP-algoritmen for å finne ut om 'P' forekommer i 'T.'

For 'p' prefiksfunksjonen, ? ble beregnet tidligere og er som følger:

Løsning:

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

Mønster 'P' har blitt funnet at kompleksitet forekommer i en streng 'T.' Totalt antall skift som fant sted for at kampen skal bli funnet er i-m = 13 - 7 = 6 skift.