.. -*- coding: utf-8; -*- .. raw:: html Knuth-Morris-Pratt法 ================================================== MP(Morris-Pratt)法 ~~~~~~~~~~~~~~~~~~~~~ MP_Shift ---------- Bord配列(:doc:`/Algorithms/Basic/border`) をミスマッチが生じた時のシフト量に用いる. j文字目で不一致になった時のシフト量を :math:`MP_Shift[j]` と定義する. :math:`MP_Shift[j] = j - Bord[j]` コード --------- Naiveな手法:bruteforce1において,ミスマッチが生じたときのシフト量は .. literalinclude:: /Scripts/Python/matching.py :lines: 23 となっており,右に一つずらすのみとなっている. MP法ではこの部分にMPShiftを用いる. 変更を加えた物は以下の様になる.  :download:`/Scripts/Python/MP.py` .. literalinclude:: /Scripts/Python/MP.py :pyobject: MP KMP(Knuth-Morris-Pratt)法 ~~~~~~~~~~~~~~~~~~~~~~~~~~ KMP法では,MP法に不一致の情報も加えたシフト量を用いる. KMP_Shift ------------ KMP_Shiftを以下の様に定義する. :math:`KMP_Shift[j] = j - Strong_Bord[j]` マッチングの実行状態を出力 ----------------------------------------- .. raw:: html



参考文献 --------- * 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