ボイヤー-ムーア文字列検索アルゴリズム
一致サフィックス規則には2つのテーブルを必要とする。1つは通常使用し、もう1つは前者が意味のある結果を返さない場合や一致が起きた場合に使う。前者のテーブルを L、後者のテーブルを H とする。これらの定義は次の通りである。
各 i について L[i] は、文字列 P[i..n] が P[1..L[i]] のサフィックスに一致し、そのサフィックスの前の文字が P[i-1] と同じでない場合の最大の値を格納する。そのような条件を満たす位置がない場合 L[i] にはゼロを格納する。
H[i] には P のプレフィックスでもある P[i..n] の最大サフィックスの長さを格納する(もしあれば)。そのような一致が存在しない場合 H[i] をゼロとする。
どちらのテーブルも構築には O(n) の時間と O(n) の領域を必要とする。提案されるシフト量は n - L[i] または n - H[i] で、H は L[i] がゼロとなるか、P 全体が一致した場合にのみ使われる。