ボイヤー-ムーア文字列検索アルゴリズム
文字列 S に対する操作を以下のように表す:
S[i]: 文字列 S の i 番目の文字
S[i..j]: 文字列 S の i から j 番目までの部分文字列(i 文字目、j 文字目をそれぞれ含む)
文字列 S に含まれる文字の個数を文字列の長さと定義する。また、文字列 S の先頭を含む部分文字列をプレフィックス、末尾を含む部分文字列をサフィックスと定義する。
len(S):S の長さ
S[1..i], 1 ≤ i ≤ len(S):S のプレフィックス
S[i..len(S)], 1 ≤ i ≤ len(S):S のサフィックス
検索文字列をパターンと呼び、P で表す。被検索文字列をテキストと呼び、T で表す。また T 上での P の位置を T の先頭から数えた P の末尾の文字の位置と定義し、k で表す。
T:テキスト(被検索文字列)
P:パターン(検索文字列)
k:テキスト T 上でのパターン P の最後の文字の位置(len(P) ≤ k ≤ len(T))
「P が T に一致する」とは P と文字列として等価な部分文字列 T[i..j] が存在することをいう。より具体的に、P が位置 k で T と一致するとは、k 番目から前方 len(P) 文字分を取り出した部分文字列 T[(k − len(P) + 1)..k] が P と文字列として等価であることをいう。
本項では特に断りない限り、m を len(T), n を len(P) の意味で使う。
不一致文字規則のためのテーブルの正確な形式によって前処理の詳細は異なるが、単純な定数時間の参照では次のようになる。まず2次元のテーブルを作る。その際、第1の添字は文字 c のアルファベット順であり、第2の添字はパターン内の文字の位置 i である。このテーブルを参照すると、P 内で c が存在する位置 j の最大値(ただし j < i)を返すか、そのような c が存在しない場合は -1 を返す。提案するシフト量は i - j または n となる。アルファベットが有限で k 個とすれば、必要な領域は O(kn)、参照時間は O(1) となる。