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

クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）<code>S</code>から単語<code>W</code>を探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt および（単独で）J. H. Morris が発明し、3人共同で発表した。本項目では文字列を表すにあたって、0 からインデックスを開始する配列を用いる。従って（後述の）単語 <code>W</code> 内の文字 <code>'C'</code> は <code>W[2]</code> と表される。