資料5

教科書 pp. 103-109の一般的な説明（文字式による一般的な記述）が、そのままわかればよいのだけど、なかなかイメージがわかないだろうとみて、資料5問2に示したような、とらえ方を示しました。
失敗関数の意味、使い方、求めかたを確認のこと。すると、自分の答えがあっていることを確認できる。
一部の提出には誤りあり。正解を確認すること。Ｃプログラムではないので文字列の先頭は1から始まる。

問5 P="abcdabc"のとき、kmp 法の失敗関数f(i)を求めよ。

X        XY
a         a            f(1) = 0 　(最初の文字から一致しないときは、0) 

aX       aX            f(2) = 1 　(1文字一致して、2文字目で不一致。Xに
ab        ab 　　　　　　　　　　　何番目の文字で再開するか）

abX      abX           f(3) = 1 
abc        abc

abcX      abcX         f(4) = 1 
abcd         abc

abcdX     abcdX        f(5) = 1
abcda         a 

abcdaX    abcdaX       f(6) = 2
abcdab        ab 

abcdabX    abcdabX      f(7) = 3
abcdabc        abc

問6
T = ababd ababc cbdca bcadb (n=20)

問5から P = abcdabc (m=7)
                a  b  c  d  a  b  c
　i             1  2  3  4  5  6  7
 f(i)           0  1  1  1  1  2  3  

失敗関数は、「Pがiの位置で失敗したら、次は、jの位置にPのどのi番目をもってきて、マッチングを再開するか」を値とする。
Text側のjは後戻りしないことに注意

(以下、j =< n-m の間だけ、調べるとした方がうまい）
(つまり、残り6文字になったら、もう比較しないで失敗。その場合の解答は、kmpは22回、naiveは 27回)
（ただし、教科書の疑似コードは、こうなっていないし、先週のnaive関数課題の解答例も、標準はこうなっていない。
このような解答をする場合は、どのようにカウントしたのかを、レポートに書いて示すほうがよい） (2022年度コメント）、

kmpでマッチング                             
ababdababccbdcabcadb
abc　　　　　　　　　　　　　3 (j=3, i=3で失敗。j=3の位置にi=1を)
  abc                        3 (j=5, i=3で失敗。j=5の位置にi=1を)
    a                        1
     abc                     3 
       abcd                  4 (j=11, i=4で失敗。j=11の位置にi=1を。一番嬉しい動き）   
          a                  1
           a                 1
            a                1
             a               1
              abcd           4   22　（ここで、やめるほうがうまい）
                 ab          2　
                  a          1
                   a         1   合計 比較回数は26    

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)         
        
tX        tX    
ta         ta       f(2) = 1

taX       taX    
tar         tar     f(3) = 1

tarX      tarX    
tart         tar    f(4) = 1

tartX     tartX    
tarta        ta     f(5) = 2

tartaX     tartaX    
tartar        tar   f(6) = 3

資料5 問8 kmpの計算量 (教科書 p. 109)

問8 kmpの時間計算量を示せ

教科書 (p. 109) に解答あり。
まず、直観的な分析をしてみよう。そのあと、教科書を読み直すこと

アルゴリズムで一番手間のかかる部分（ループになっている部分）は、どんな処理か。計算時間に一番影響を与える処理はどこか。
どんな場合に、最悪になるか。

以下では、まず失敗関数を求める計算時間を除いて考える

失敗関数が求められたあとのkmp法の計算量

Tの長さnや、Pの長さmが増えたら、計算時間は、どのように増加するだろうか。

kmp法が、最悪の比較回数となるのは、どんな場合だろう。
Tの位置を示す j は後戻りしないのだから、「部分照合した後、失敗関数によって i が大きいまま、つまり、Pがあまり前進できない場合」が問題となるだろう。

アルゴリズムをなぞれるようになって考えてみると、最悪のケースの例は、「Pの i が k 文字進んだところで不一致。j はそのままに、Pは k-1 から再開」を繰り返すTとPだ。

たとえば、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回)

上のTとPでは、Tの長さ n に比例して、計算時間が増加する。したがってO(n)

Pの失敗関数を求めるアルゴリズムの計算量

失敗関数を求めるアルゴリズムの計算時間は、Pの長さmに比例する。O(m)
この結果を得るには、巧いアルゴリズムである疑似コードを分析する必要がある。
私たちがアルゴリズムをなぞる場合は、目による視覚的な演算をしてしまっている。視覚的演算は速いので気が付かないが、各iについて、毎回下のPを先頭から動かしているようだと、二重ループになってしまっているので、O(m)ではない。

したがって、失敗関数を準備してから、kmp照合を行うプログラムの計算時間全体はO(m + n)である。
通常、パターンPの長さmは、テキストTの長さnと比較すると、非常に小さいので O(n)。