KMPは、不一致が生じたときに、次の一致がどこで始まるかを決定するのに十分な情報を有するという観察を利用して、主な「文字列」 S内の「単語」 Wの出現を検索するパターンマッチングアルゴリズムである。この情報を利用して、われわれが知っている文字と一致することを避けてください。パターンを検索するための最悪の複雑さは、 O(n)に減少します。