クヌース–モリス–プラット法
テーブル生成アルゴリズムの計算量は O(n)(ここで n は W の長さ)である。初期化コードを除くと処理は全て while ループ内で行われるので、このループを O(n) 回実行することを示せばよい。これは i と i - j の値を考えていくことで明らかとなる。第一の分岐では i - j は変化せず、i と j が同時にインクリメントされる。第二の分岐では j が T[j] で置換される。これは既に述べたように j より常に小さい。従って i - j は増加する。第三の分岐では、i だけがインクリメントされる。つまり、i も i - j も増加する。i ≥ i - j であるので、これは各段階で i か i の下限が増加するのと同じことである。このアルゴリズムは i = n となったとき終了し、i - j の初期値は 1 なので、ループは最大で 2n 回くりかえされる。以上からテーブル生成アルゴリズムの計算量は O(n) となる。
W = "ABCDABD" の例を考えてみよう。まず T[0] = -1 とする。T[1] は単語の2文字目で不一致となった場合のバックトラックする文字数であるが、1文字しか一致していない状態ではバックトラックできないので、T[1] = 0 となる。
T[2] は、そこまでの文字列 "AB" にその文字列の先頭部分と等しいサブ文字列がないため T[2] = 0 となる。
T[3] についても同様の判定を行う。つまり、T[i] を検討する場合、W[0] から W[i-1] までの文字列について、W[i-1] で終わる文字列と W[0] から始まる文字列が一致するかどうかを調べる。しかし、長さ 2 の文字列(考えられる最長のサブ文字列)が一致するなら、それは T[2] の段階で見つかっていたはずである。従って長さ 2 のサブ文字列はありえない。また、長さ 1 では "C" は "A" とは一致しない。以上のことから T[3] = 0 とする。