ラビン-カープ文字列検索アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:28 UTC 版)
ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種[1][2]。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。
| ||||||||||||||||||||||||||||||||||||||
- ^ Karp と Rabin のオリジナル論文: Karp, Richard M.; Rabin, Michael O. (1987年3月). "Efficient randomized pattern-matching algorithms". IBM Journal of Research and Development 31 (2), 249-260.
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001年. ISBN 0-262-03293-7. Section 32.2: The Rabin-Karp algorithm, pp.911–916.
[続きの解説]
「ラビン-カープ文字列検索アルゴリズム」の続きの解説一覧
- 1 ラビン-カープ文字列検索アルゴリズムとは
- 2 ラビン-カープ文字列検索アルゴリズムの概要
- 3 ラビン-カープと複数パターン検索
ラビンカープ文字列検索アルゴリズムと同じ種類の言葉
| アルゴリズムに関連する言葉 | 乱択アルゴリズム 進化的アルゴリズム ラビンカープ文字列検索アルゴリズム ビタービアルゴリズム 分散アルゴリズム(ぶんさんあるごりずむ) |
- ラビンカープ文字列検索アルゴリズムのページへのリンク
