TechCodeview

Knuth-Morris og Pratt introducerer en lineær tidsalgoritme til strengmatchningsproblemet. En matchningstid på O (n) opnås ved at undgå sammenligning med et element af 'S', der tidligere har været involveret i sammenligning med et eller andet element i mønsteret 'p', der skal matches. dvs. tilbagesporing på strengen 'S' forekommer aldrig

Komponenter i KMP-algoritmen:

1. Præfiksfunktionen (Π): Præfiksfunktionen, Π for et mønster indkapsler viden om, hvordan mønsteret matcher mod skiftet af sig selv. Denne information kan bruges til at undgå en ubrugelig ændring af mønsteret 's.' Med andre ord, dette gør det muligt at undgå tilbagesporing af strengen 'S.'

2. KMP-kampene: Med streng 'S', mønster 'p' og præfiksfunktionen 'Π' som input, find forekomsten af ​​'p' i 'S' og returnerer antallet af skift af 'p', hvorefter forekomster findes.

Præfiksfunktionen (Π)

Følgende pseudokode beregner præfiksfunktionen, Π:

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

Analyse af løbetid:

I ovenstående pseudokode til beregning af præfiksfunktionen kører for-løkken fra trin 4 til trin 10 'm' gange. Trin 1 til trin 3 tager konstant tid. Derfor er driftstiden for beregningspræfiksfunktionen O (m).

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

indsætte i tastaturet

Løsning:

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

Efter iteration 6 gange er præfiksfunktionsberegningen færdig:

KMP matcher:

KMP Matcheren med mønsteret 'p', strengen 'S' og præfiksfunktionen 'Π' som input, finder et match af p i S. Følgende pseudokode beregner den matchende komponent af 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 

Analyse af løbetid:

For-løkken, der begynder i trin 5, kører 'n' gange, dvs. så lang som længden af ​​strengen 'S.' Da trin 1 til trin 4 tager konstante tider, domineres køretiden af ​​dette for løkken. Køretiden for matchningsfunktionen er således O (n).

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

Lad os udføre KMP-algoritmen for at finde ud af, om 'P' forekommer i 'T.'

For 'p' præfiksfunktionen, ? blev beregnet tidligere og er som følger:

Løsning:

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

Mønster 'P' har vist sig at kompleksitet forekommer i en streng 'T.' Det samlede antal skift, der fandt sted for at matchen skulle findes, er i-m = 13 - 7 = 6 skift.