クヌース–モリス–プラット法
前述の実施例はこのアルゴリズムのあらゆる要素を含んでいる。ここで、現在の照合が不一致に終わった際に次の照合の開始時点で参照する「部分マッチ」テーブル T を使用するものとする(後述)。T のエントリは、S[m] から照合して S[m + i] と W[i] が不一致となった際に次に照合を開始すべき位置を S の m + i - T[i] 番目とするよう設定される(つまり、T[i] は不一致の際のバックトラッキングを示す)。これには2つの意味がある。第一に T[0] = -1 は W[0] が不一致の場合にバックトラックできず単に次の文字を照合すべきであることを示す。第二に m + i - T[i] が次の照合のインデックスとなるが、その先頭 T[i] 個の文字を照合する必要はなく、照合は W[T[i]] からでよい。以下の擬似コードは KMP法の実装例である。