文字列探索アルゴリズムの一種で、発明者2名の名前を冠しています。KMP法と同様に、予め余計な探索をを行わなくて済むようにずらし表を作成する必要があります。KMP法では理論上高速とされるわりに実用上速度が出にくいという欠点がありましたが、BM法は実用上高速に動作するとされています。KMP法との大きな違いは、探索するパターン文字列の先頭ではなく、末尾から照合を行うという点にあります。末尾が一致しなければ、パターン文字数分一気に探索位置を飛ばすことができるかもしれません。前述のとおり、このアルゴリズムの特徴はずらし表と末尾から照合です。ずらし表では、不一致の際に探索対象文字列の位置をどこまでずらすかをあらかじめ準備しておく表です。探索する場合のものです。BM法ではこのような順で探索を進めます。1回目の探索は末尾の位置で不一致になります。この際不一致になった文字がパターン文字列に含まれないため、一気にパターン文字列分探索位置を進めることができます。これはパターンに含まれない文字のため、これを含む位置はすべて調べるまでもなく不一致になると言えるからです。文字で不一致になります。対応する値を取得しずらします。3回目の探索でも同じようにパターン末尾の文字から一致判定を行います。順にすべて一致するためここで処理終了となります。探索の前に予めずらし表を生成して置かなければなりません。これは単純にパターン文字列の末尾からの距離で表します。同じ文字が出てくる場合、より後ろの位置(ずらす大きさが小さい値)を優先します。場合、次のようになります。各文字の末尾からの距離は次のようになるので、これの各文字での最小値をとったものがずらし表となります。0以下がそのずらし表です。ずらし表に存在しない文字(つまりパターン文字列に存在しない文字)の場合、パターン文字列文の長さがずらす大きさになります。探索対象文字列の文字数を越えない条件でループします。パターン文字列末尾の位置にします。末尾からパターン文字と一致するか判定を行います。