クヌース–モリス–プラット法

ウィキペディア

クヌース–モリス–プラット法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/30 08:10 UTC 版)

クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。