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

読み方、または別称：

Rabin-Karp String Search Algorithm

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

ラビン-カープ文字列検索アルゴリズム（Rabin-Karp String Search Algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごく稀に最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。

• 出典: フリー百科事典『ウィキペディア（Wikipedia）』
• [ ラビン-カープ文字列検索アルゴリズムの改定履歴 ]