Knuth-Morris en Pratt introduceren een lineair tijdalgoritme voor het stringmatchingprobleem. Een aanpassingstijd van O (n) wordt bereikt door vergelijking met een element van 'S' dat eerder betrokken is geweest te vermijden in vergelijking met een element van het patroon 'p' dat moet worden aangepast. d.w.z. het teruggaan naar de string 'S' vindt nooit plaats

Onderdelen van het KMP-algoritme:

1. De prefixfunctie (Π): De Prefix-functie, Π voor een patroon, omvat kennis over hoe het patroon overeenkomt met de verschuiving van zichzelf. Deze informatie kan worden gebruikt om een ​​nutteloze verschuiving van het patroon 'p.' te voorkomen. Met andere woorden, dit maakt het mogelijk om het teruglopen van de string 'S.' te vermijden.

2. De KMP-wedstrijden: Zoek met string 'S', patroon 'p' en prefixfunctie 'Π' als invoer het voorkomen van 'p' in 'S' en retourneert het aantal verschuivingen van 'p' waarna gevonden exemplaren zijn gevonden.

De prefixfunctie (Π)

Bereken volgens pseudocode de prefixfunctie, Π:

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

Looptijdanalyse:

In de bovenstaande pseudocode voor het berekenen van de prefixfunctie loopt de for-lus van stap 4 tot en met stap 10 'm' keer. Stap 1 tot en met Stap 3 nemen constante tijd in beslag. Daarom is de looptijd van de berekeningsvoorvoegselfunctie O (m).

Voorbeeld: Bereken Π voor het patroon 'p' hieronder:

verschil tussen programma en script

Oplossing:

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

Na zes iteraties is de berekening van de prefixfunctie voltooid:

De KMP-wedstrijden:

De KMP Matcher met het patroon 'p', de string 'S' en de voorvoegselfunctie 'Π' als invoer, vindt een overeenkomst van p in S. Bereken met behulp van pseudocode de overeenkomende component van het KMP-algoritme:

 <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 

Looptijdanalyse:

De for-lus die begint in stap 5 loopt 'n' keer, d.w.z. zo lang als de lengte van de string 'S.' Omdat stap 1 tot en met stap 4 constante tijden duren, wordt de looptijd voor de lus hierdoor gedomineerd. De looptijd van de matchingfunctie is dus O (n).

Voorbeeld: Gegeven een string 'T' en patroon 'P' als volgt:

Laten we het KMP-algoritme uitvoeren om te bepalen of 'P' voorkomt in 'T.'

Voor 'p' is de prefixfunctie ? werd eerder berekend en is als volgt:

Oplossing:

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

Er is ontdekt dat patroon 'P' complexiteit voorkomt in een string 'T.' Het totaal aantal diensten dat heeft plaatsgevonden voor de te vinden match is i-m = 13 - 7 = 6 diensten.