ラビン-カープ文字列検索アルゴリズム

ラビン-カープ文字列検索アルゴリズム（Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。ラビン-カープの単純な応用例として、盗作の検出がある。例えば、学生が『白鯨』に関する英語の論文を書いたとしよう。賢い教授は『白鯨』に関する様々な資料を集め、それらの全文を自動的に抽出するものとする。そこで、ラビン-カープを使えば学生の論文の任意の文がそれら資料からの丸写しかどうかを判定できる。微妙な修正で盗作を判定できなくなるのを防ぐには、大文字・小文字の別を無視し、句読点を無視すればよい。この場合の検索文字列数 k は膨大なので、単一文字列検索アルゴリズムは非現実的である。