問5 P="abcdabc"のとき、kmp 法の失敗関数f(i)を求めよ。 X XY a a f(1) = 0 (最初の文字から一致しないときは、0) aX aX f(2) = 1 (1文字一致して、2文字目で不一致。Xに ab ab 何番目の文字で再開するか) この先は、MaNaBoへ
問6 T = ababd ababc cbdca bcadb (n=20) 問5から P = abcdabc (m=7)の失敗関数が求められているとする。 失敗関数は、「Pがiの位置で失敗したら、次は、jの位置にPのどのi番目をもってきて、マッチングを再開するか」を値とする。 Text側のjは後戻りしないことに注意 (以下、j =< n-m の間だけ、調べるとした方がうまい) kmpでマッチング ababdababccbdcabcadb abc 3 (j=3, i=3で失敗。j=3の位置にi=1を) abc 3 (j=5, i=3で失敗。j=5の位置にi=1を) 続きは、MaNaBoへ naiveでマッチング ababdababccbdcabcadb abc 3(j=3,i=3で失敗。j=2の位置にi=1。jも戻っているのがnaive) a 1 abc 3 a 1 a 1 abc 3 12 a 1 13 abcd 4 17 a 1 a 1 a 1 20 a 1 a 1 a 1 23 abcd 4 27 a 1 a 1 ab 2 a 1 a 1 合計 33
問7 P = "tartar"とする。kmp 法の失敗関数f(i)を求めよ。 失敗関数f(i)を求める X XY t t f(1) = 0 (最初の文字から一致しないときは、0) 続きはMaNaBoへ
問8 kmpの時間計算量を示せ
失敗関数が求められたあとのkmp法の計算量
たとえば、T="aaaaa", P="ab"(Pの失敗関数はf(1)=0, f(2)=1) aaaaa ab i=1, i=2, j = 1, j = 2 ab i=1, i=2, j = 3 ab i=1, i=2, j = 4 ab i=1, i=2, j = 5 a b i=1, i=2, j = 6 > n 終了 この場合、Tとの比較回数は2n - 1回 (9回) (下の場合も、aabと進んで、abと比較を繰り返すが、最悪ではない) aaaaa aab aab aab aa b (3+2+2+1 = 8回) aaaaa aaab aaab aaa b (4+2+1 = 7回)
Pの失敗関数を求めるアルゴリズムの計算量