ボイヤー-ムーア文字列検索アルゴリズム
1979年、Zvi Galil はボイヤー-ムーア法に単純だが重要な改良を施した。追加されたガリル規則はシフト量を決めるものではなく、各位置での照合を高速化するものである。位置 k1 で P と T を照合して T 上の文字 c まで照合し、次にシフトした位置 k2 によりパターンの先頭の位置が c と k1 の間になったとき、P のプレフィックスは部分文字列 T[(k2 - n)..k1] と必ず一致する。したがってこの際の文字照合は T の k1 の位置まででよく、k1 より前の照合は省略できる。ガリル規則はボイヤー-ムーア法の効率を向上させるだけでなく、最悪ケースでも線型時間であることを保証するのに必須である。