クヌース–モリス–プラット法
次に W[4] つまり 'A' を渡す。同様の考え方で考慮すべき最長のサブ文字列の長さは 1 であり、この場合 'A' は単語の先頭と一致している。しかし、テーブルには現在位置の「直前」のサブ文字列長を格納するので、T[4] = 0 となる。
次に W[5] を調べると 'B' である。ここで W[4] から W[5] のサブ文字列は単語の先頭サブ文字列に等しい。従って W[5] で不一致となった場合に W[4] 以前に対応する部分を再度照合する必要はない。そこで T[5] = 1 となる。
現在注目している W[4] = 'A' から始まる文字列の次の文字は 'B' であることが期待されるが、これは W[5] と等しい。さらに前述の通り W[6] のためのサブ文字列を探索するのに W[4] より前を考慮する必要はない。従って、T[6] = 2 となる。
以上から、この場合のテーブルは以下のように生成される:
このアルゴリズムの各部分は(上述の通り)それぞれ O(k) と O(n) の計算量があるので、全体としての計算量は O(n + k) となる。
先述の実施例でも明らかなように、文字をスキップできればできただけ単純な文字列検索アルゴリズムよりも有利となる。つまり、バックトラックがない方が好ましい。換言すれば T が全て 0 になっていればよい。従って "ABCDEFG" のような単語ではこのアルゴリズムは最も効率的に動作し、その際のテーブルは先頭が -1 でそれ以外は全て 0 となっている。逆に W = "AAAAAAA" のような場合は最悪である。このときのテーブルは以下のようになる。
これは T の最悪のパターンであり、S = "AAAAAABAAAAAABAAAAAAA" といった単語にもあてはまる。S の中に "AAAAAAB" が出現する頻度が多いほど繰り返し回数が増える。この単語のテーブル生成は高速となるが、検索は複数回行われる可能性があるのに対して、テーブル生成は1回だけである。従って、このような単語を検索する場合、このアルゴリズムの性能は低下する。ちなみに、このような文字列はボイヤー-ムーア法では最高の性能となる。KMP法は最良でも最悪でも線形時間で検索が完了するのに対して、ボイヤー-ムーア法は最良と最悪で大きく時間が異なる。