.. -*- 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