Knuth-Morris-Pratt法

MP(Morris-Pratt)法

MP_Shift

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

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

コード

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

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

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

KMP(Knuth-Morris-Pratt)法

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

KMP_Shift

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

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

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

text =
pattern =
KMPを使う

参考文献

• D.E. Knuth, J.H. Morris, and V.R. Pratt, “Fast pattern matching in strings.” SIAM Journal on Computing, Volume 6, Issue 2, pp.323-350, 1977 <http://www.mendeley.com/research/fast-pattern-matching-in-strings/>