TechCodeview

Knuth-Morris a Pratt zavádzajú lineárny časový algoritmus pre problém porovnávania reťazcov. Čas zhody O (n) sa dosiahne tým, že sa vyhneme porovnávaniu s prvkom „S“, ktorý bol predtým zahrnutý v porovnaní s niektorým prvkom vzoru „p“, ktorý sa má porovnávať. t.j. spätné sledovanie reťazca 'S' nikdy nenastane

Komponenty algoritmu KMP:

1. Funkcia prefixu (Π): Funkcia predpony, Π pre vzor zahŕňa poznatky o tom, ako sa vzor zhoduje so samotným posunom. Táto informácia môže byť použitá, aby sa zabránilo zbytočnému posunu vzoru 'p.' Inými slovami, toto umožňuje vyhnúť sa spätnému sledovaniu reťazca 'S.'

2. Zápasy KMP: S reťazcom 'S', vzorom 'p' a funkciou predpony 'Π' ako vstupmi nájdite výskyt 'p' v 'S' a vráti počet posunov 'p', po ktorých sa nájdu výskyty.

Funkcia predpony (Π)

Nasledujúci pseudokód vypočíta funkciu 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 chodu:

Vo vyššie uvedenom pseudokóde na výpočet funkcie prefixu cyklus for od kroku 4 do kroku 10 prebehne „m“ krát. Kroky 1 až 3 trvajú konštantne. Preto je doba trvania výpočtovej prefixovej funkcie O (m).

Príklad: Vypočítajte Π pre vzor „p“ nižšie:

java objektová rovnosť

Riešenie:

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

Po 6-krát iterácii je výpočet funkcie prefixu dokončený:

KMP sa zhoduje:

KMP Matcher so vzorom 'p', reťazcom 'S' a prefixovou funkciou 'Π' ako vstupom nájde zhodu p v S. Nasledujúci pseudokód vypočíta zodpovedajúci komponent 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 chodu:

Cyklus for začínajúci v kroku 5 beží „n“ krát, t. j. tak dlho, ako je dĺžka reťazca „S“. Keďže krok 1 až krok 4 trvá konštantné časy, pre slučku dominuje čas behu. Čas priebehu párovacej funkcie je teda O (n).

Príklad: Daný reťazec „T“ a vzor „P“ takto:

Vykonajme algoritmus KMP, aby sme zistili, či sa 'P' vyskytuje v 'T.'

Pre 'p' funkciu predpony, ? bola vypočítaná predtým a je nasledovná:

Riešenie:

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

Zistilo sa, že zložitosť vzoru 'P' sa vyskytuje v reťazci 'T.' Celkový počet posunov, ktoré sa uskutočnili na nájdenie zhody, je i-m = 13 - 7 = 6 posunov.