クヌース–モリス–プラット法
実際にこのアルゴリズムがどのように動作するかを見てみよう。このアルゴリズムの状態は二つの整数 m と i で表される。m はテキスト S 内の文字の位置であり、単語 W にマッチする可能性のある位置でもある。i は、その時点で照合中の W 内の文字の位置を示す。検索開始時点の状態は以下のように表される。
まず、上記の状態で W の先頭と S の先頭から照合していく。この例では4文字目の照合で S[3] が空白、W[3] = 'D' となるため、不一致となる。W 内でそこまでに照合された範囲で 'A' が 0 番目にしかないことから、そこまで照合した S の範囲内に 'A' が出現しないことは明らかである。つまり、S[1] から S[3] までは W[0] とマッチすることはない。そのため、次の照合を単純に S[1] から開始するのではなく、m = 4 および i = 0 として次の照合を開始する。