TechCodeview

Knuth-Morris és Pratt egy lineáris idő algoritmust vezet be a karakterláncillesztési problémára. Az O (n) illesztési idejét úgy érjük el, hogy elkerüljük az „S” olyan elemével való összehasonlítást, amely korábban részt vett a „p” minta egyes elemeivel összehasonlítva. azaz az „S” karakterláncon soha nem fordul elő visszalépés

A KMP algoritmus összetevői:

1. Az előtag függvény (Π): A minta Π előtagfüggvénye azt a tudást foglalja magában, hogy a minta hogyan illeszkedik önmaga eltolódásához. Ez az információ felhasználható a „p” minta haszontalan eltolásának elkerülésére. Más szavakkal, ez lehetővé teszi az „S” karakterlánc visszalépésének elkerülését.

2. A KMP mérkőzései: Az „S” karakterlánc, a „p” minta és a „Π” előtagfüggvény bemeneteként megkeresi a „p” előfordulását „S”-ben, és visszaadja a „p” eltolódásainak számát, amelyek után az előfordulásokat megtalálja.

Az előtag függvény (Π)

A pszeudokódot követően számítsa ki az előtagfüggvényt, Π:

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

Futási idő elemzése:

A fenti pszeudokódban az előtagfüggvény kiszámításához a for ciklus a 4. lépéstől a 10. lépésig „m”-szer fut le. Az 1–3. lépés állandó időt vesz igénybe. Ezért az előtag függvény számítási ideje O (m).

Példa: Számítsa ki a Π-t az alábbi 'p' mintához:

vb és vb net

Megoldás:

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

Hatszori iteráció után az előtagfüggvény számítása befejeződött:

A KMP mérkőzései:

A KMP Matcher a „p” mintával, az „S” karakterlánccal és a „Π” előtagfüggvénnyel bemenetként megtalálja a p egyezését S-ben. A pszeudokódot követően számítsa ki a KMP-algoritmus egyező komponensét:

 <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 

Futási idő elemzése:

Az 5. lépésben kezdődő for ciklus 'n'-szer lefut, azaz addig, amíg az 'S' karakterlánc hossza. Mivel az 1-től a 4-ig lépések állandó időt vesznek igénybe, a ciklus futási idejét ez uralja. Így az illesztő függvény futási ideje O (n).

Példa: Adott egy „T” karakterlánc és „P” minta a következőképpen:

Végezzük el a KMP algoritmust, hogy megtudjuk, előfordul-e 'P' a 'T'-ben.

'p' esetén az előtag függvény, ? korábban kiszámolták, és a következő:

Megoldás:

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

A „P” minta bonyolultnak találta a „T” karakterláncban. A talált egyezéshez lezajlott műszakok száma összesen i-m = 13 - 7 = 6 műszak.