-2-Horspoolのアルゴリズム、Sundayのアルゴリズムでは、不一致となったときに参照する文字を変えることで、実用上の平均計算時間が改善する。規則というものを導入すればよい。一定の長さの文字列をハッシュ化(1つの整数)にした上で、ハッシュ値で検索するアルゴリズム。複数ある場合でも、文字列長が同じであれば事前計算結果を使い回せる。$O(|S|)$もう少し詳細KMP法やBM法がマッチ位置を試す回数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字列同士の照合を高速化する。開始位置を1つずつずらして作成しておく。