Boyer-Moore法

照合方法

Algorithm BM(Jewels of Stringology P.28) /Scripts/Python/BM.py

j文字目で不一致になった時のシフト量を　\(BM＿Shift[j]\) と定義する．

シフト量の計算

与えられたパターンのBMShiftの計算

計算に 周期 (period)　を用いる．

PREF[i]を用いたS[i]の計算

注釈

\(PREF[i] = max\) { \(j:pat[i...i+j-1]がpatの\) 接頭辞 (prefix) }

\(S[i]\)　i番目で終わる部分文字列とパターンの共通接尾辞の最大長

PREF[i]の計算（素朴な方法）

S[i]を用いた　周期 (period)　の計算

マッチングの実行状態を出力(作成中)

text =
pattern =

参考文献

• R.S. Boyer and J.S. Moore, “A fast string searching algorithm.”, Communications of the ACM, Volume 20, Issue 10, pp.762-772, 1977 <http://dl.acm.org/citation.cfm?id=359859>