テーブル生成法の実施例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/08 01:52 UTC 版)
「クヌース–モリス–プラット法」の記事における「テーブル生成法の実施例」の解説
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 とする。 次に 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 となる。 以上から、この場合のテーブルは以下のように生成される: i0 1 2 3 4 5 6 W[i]A B C D A B D T[i]-1 0 0 0 0 1 2
※この「テーブル生成法の実施例」の解説は、「クヌース–モリス–プラット法」の解説の一部です。
「テーブル生成法の実施例」を含む「クヌース–モリス–プラット法」の記事については、「クヌース–モリス–プラット法」の概要を参照ください。
- テーブル生成法の実施例のページへのリンク
