ボイヤー-ムーア文字列検索アルゴリズム
ボイヤー-ムーア法は T における P の出現を検索するもので、異なる位置で明示的に何度も文字を比較することで検索する。全部で m − n + 1 ある位置について力まかせ探索するのではなく、P を前処理して得た情報を使ってなるべく位置をスキップする。
まず、k = n として P が T の先頭に配置されるようにする。そして P の n 番目と T の k 番目から文字を照合しはじめ、インデックスを順次小さくして照合していく。つまり、P の最後尾から先頭に向かって照合していく。この照合は不一致が発生するか P の先頭に到達するまで行われ(その場合は一致が見つかったことになる)、その後いくつかの規則に従って位置を右にシフトできる最大値を求める。新たな位置で再び同様の照合を行い、T の最後尾に到達するまでそれを繰り返す。
シフト規則は、P の前処理で生成したテーブル群を参照することで実装されており、定数時間でシフト量が決定される。
オリジナルの論文では、パターンがテキスト内に存在しない場合のボイヤー-ムーア法の最悪ケースは O(n+m) だとされている。これは1977年、ドナルド・クヌース、James H. Morris、Vaughan Pratt が初めて証明した。さらに1980年、Leonidas J. Guibas と Andrew Odlyzko が最悪ケースの文字比較回数の上限を 5m 回以下だと証明した。1991年、Coleは最悪ケースの比較回数の上限が 3m 回以下であることを証明した。
パターンがテキスト内に出現する場合、オリジナルのアルゴリズムの最悪ケースは O(nm) となる。これはパターンもテキストも同じ文字の羅列の場合に容易に発生する。ただし、ガリル規則を加えるとあらゆるケースで線型時間となる。