ラビン-カープ文字列検索アルゴリズム
ラビン-カープは最悪の場合に非常に低速であるため、単一の文字列検索ではクヌース-モリス-プラット法やボイヤー-ムーア文字列検索アルゴリズムよりも劣っている。しかし、ラビン-カープは複数パターン検索の場合に使われることが多い。
すなわち、テキストから k 種類の固定長パターンのいずれかと一致する部分を検索する場合、ブルームフィルタや集合を使ってラビン-カープを修正し、ある文字列がパターンの集合のいずれかと一致するかどうかを調べるようにすることができる。
全てのサブ文字列は固定長 m であるとする。
他のアルゴリズムは単一のパターンの検索を O(n) の時間で行うので、k 個のパターンの検索には O(n k) の時間がかかる。一方、修正したラビン-カープでは k 個のパターンの検索を O(n+k) の時間で実行することが期待できる。というのもサブ文字列のハッシュ値と全パターンのいずれかのハッシュ値との一致の検出は O(1) の時間で可能だからである。