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法に不一致の情報も加えたシフト量を用いる.
マッチングの実行状態を出力¶
参考文献¶
- 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/>