TechCodeview

Knuth-Morris och Pratt introducerar en linjär tidsalgoritm för strängmatchningsproblemet. En matchningstid för O (n) uppnås genom att undvika jämförelse med ett element av 'S' som tidigare har varit involverat i jämförelse med något element i mönstret 'p' som ska matchas. d.v.s. backtracking på strängen 'S' inträffar aldrig

Komponenter i KMP-algoritmen:

1. Prefixfunktionen (Π): Prefixfunktionen, Π för ett mönster kapslar in kunskap om hur mönstret matchar mot förskjutningen av sig själv. Denna information kan användas för att undvika en värdelös förändring av mönstret 's.' Med andra ord, detta gör det möjligt att undvika bakåtspårning av strängen 'S.'

2. KMP-matchningarna: Med strängen 'S', mönstret 'p' och prefixfunktionen 'Π' som indata, hitta förekomsten av 'p' i 'S' och returnerar antalet skift av 'p' efter vilka förekomster hittas.

Prefixfunktionen (Π)

Följande pseudokod beräkna prefixfunktionen, Π:

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

Körtidsanalys:

I ovanstående pseudokod för beräkning av prefixfunktionen, körs for-slingan från steg 4 till steg 10 'm' gånger. Steg 1 till steg 3 tar konstant tid. Följaktligen är drifttiden för beräkningsprefixfunktionen O (m).

Exempel: Beräkna Π för mönstret 'p' nedan:

var finns webbläsarinställningarna

Lösning:

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

Efter iteration 6 gånger är prefixfunktionsberäkningen klar:

KMP-matcherna:

KMP-matcharen med mönstret 'p', strängen 'S' och prefixfunktionen 'Π' som indata, hittar en matchning av p i S. Följande pseudokod beräknar matchningskomponenten i 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 

Körtidsanalys:

For-slingan som börjar i steg 5 körs 'n' gånger, d.v.s. lika lång som längden på strängen 'S.' Eftersom steg 1 till steg 4 tar konstanta tider, domineras löptiden av detta för slingan. Sålunda är körtiden för matchningsfunktionen O (n).

Exempel: Givet en sträng 'T' och mönster 'P' enligt följande:

Låt oss köra KMP-algoritmen för att ta reda på om 'P' förekommer i 'T'.

För 'p' prefixfunktionen, ? beräknades tidigare och är som följer:

Lösning:

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

Mönster 'P' har visat sig vara komplext i en sträng 'T.' Det totala antalet skift som skett för att matchen ska hittas är i-m = 13 - 7 = 6 skift.