ボイヤー・ムーア法(BM法) - Algoful

ボイヤー・ムーア法 ボイヤー・ムーア法 (BM法) は文字列探索アルゴリズムの一種で、発明者2名の名前を冠しています。 KMP法と同様に、予め余計な探索をを行わなくて済むようにずらし表を作成する必要があります。KMP法では理論上高速とされるわりに実用上速度が出にくいという欠点がありましたが、BM法は実用上高速に動作するとされています。 KMP法との大きな違いは、探索するパターン文字列の先頭ではなく、末尾から照合を行うという点にあります。例えば末尾が一致しなければ、パターン文字数分一気に探索位置を飛ばすことができるかもしれません。 特徴 前述のとおり、このアルゴリズムの特徴はずらし表と末尾から照合です。ずらし表では、不一致の際に探索対象文字列の位置をどこまでずらすかをあらかじめ準備しておく表です。 以下の表は "AAAXABAABBCAC" から "ABBC" を探索する場合のものです。BM