Knuth-Morris-Pratt法

MP(Morris-Pratt)法

MP_Shift

Bord配列(境界 (border)) をミスマッチが生じた時のシフト量に用いる． j文字目で不一致になった時のシフト量を　\(MP＿Shift[j]\) と定義する．

\(MP＿Shift[j] = j - Bord[j]\)

コード

Naiveな手法：bruteforce1において，ミスマッチが生じたときのシフト量は

        i = i + 1

となっており，右に一つずらすのみとなっている．

MP法ではこの部分にMPShiftを用いる． 変更を加えた物は以下の様になる．　 /Scripts/Python/MP.py

KMP(Knuth-Morris-Pratt)法

KMP法では,MP法に不一致の情報も加えたシフト量を用いる．

KMP_Shift

KMP_Shiftを以下の様に定義する．

\(KMP＿Shift[j] = j - Strong＿Bord[j]\)

マッチングの実行状態を出力




参考文献