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) の計算
マッチングの実行状態を出力(作成中)¶
参考文献¶
- 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>