KMP法（クヌース・モリス・プラット法）

文字列探索アルゴリズムの一つ。パターン文字列の前処理で不一致時の移動量を示す失敗関数テーブルを作成し、テキスト上のポインタを戻さずに探索を続行する。最悪ケースでもO(n+m)の計算量を保証する。

パターンの末尾から先頭に向かって文字を比較する文字列探索のアルゴリズム。不一致になったテキストの文字がパターンのどこにあるか（不一致文字規則）や、すでに一致した末尾の部分（一致接尾辞規則）をもとに、パターンを一度に大きくずらせる。パターンが長く文字の種類が多いほど比較の回数が少なくなり、実用上は高速なので、テキストエディタの検索などに使われる。

文字列の検索、照合、置換、比較などを行うアルゴリズム。長い文字列の中から特定のパターンを探す文字列照合では、1文字ずつずらして比べる力まかせ法のほか、不一致の情報を使ってずらす幅を大きくするKMP法やBM法がある。