[分享] KMP(Knuth–Morris–Pratt algorithm)

[math120908 (小小郭)]

因為好像很多人還是不太懂，所以就嘗試PO篇文解釋一下KMP~~

如果有哪裡寫錯煩請告知>w<

---

為了方便說明我先定義一些符號:
字串(string)
   一個字串S = a_1 a_2 a_3 … a_n 是一個字母組成的sequence(序列)
   其中定義S[1] = a_1,
           S[2] = a_2,
           ...
           S[i] = a_i.

子字串(substring)
   S[i:j]就表示 a_i a_i+1 … a_j-1 a_j //假設i<=j
   我們稱S[i:j]為S的子字串，當然特別有S = S[1:n]。

   EX: aaaab 就是 aaaaaabbb 的一個子字串

前綴(prefix)
   一個字串是長這樣子的話S = |--------------|
   那                    S'= |------|         S'就是S的一個prefix

   嚴格來說如果一個字串是S = S[1:n]
   那                    S'= S[1:i] 當i<=n時，S;就是S的一個prefix

   EX: a,ab,abc,abcd,abcde,abcdef 都是 abcdef 的前綴。

F函數
   從字串S中的i位置往前延伸，最多可以往前幾位(< i)
   使得往前的這個位數是S的前綴。

   嗯看起來非常繞口的一句話= =...
   從數學上來看就是最大的滿足S[i‐F(i)+1:i] = S[1:F(i)]的數 且 F(i)<i
   不過如果不存在F(i) 就假設他 = 0吧～

   想必還是不懂所以就舉個例子吧：

       1 2 3 4 5 6 7 8 9 (index)
   S = a b a b a a b a b
       0 0 1 2 3 1 2 3 4 (F函數)

   如果還是不懂 就我們一個一個來看@_@

   F(1) = 0 因為 a babaabab
                   ababaabab

   F(2) = 0 因為 ab abaabab
                    ababaabab

   F(3) = 1 因為 aba baabab
                   a babaabab

   F(4) = 2 因為 abab aabab
                   ab abaabab

   F(5) = 3 因為 ababa abab
                   aba baabab
   注意!雖然有       a babaabab 這樣子也可以match 但是不是最長前綴

   F(6) = 1 因為 ababaa bab
                      a babaabab

   F(7) = 2 因為 ababaab ab
                      ab abaabab

   F(8) = 3 因為 ababaaba b
                      aba baabab
                        a babaabab 也是但是不是最長

   F(9) = 4 因為 ababaabab
                      abab aabab
                        ab abaabab 也是但是不是最長

看了一堆例子之後想必對F函數有點感覺了吧= =+
而這個F函數其實就是ＫＭＰ的精隨!!

假設上面例子：如果 上面叫實體字串 下面叫虛擬字串
那當我們在配對實體字串的時候 同時也在配對虛擬字串!!

意思就是我們在配對S[1:i]的時候 同時也配對了S[1:F(i)]
遞迴的來說 我們也同時配對了S[1:F(F(i))]也配對了S[1:F(F(...F(i)...))]
（假設後面那項都>0的話）

就像F(9)在配對S[1:9]時 同時也配對S[1:F(9)] = S[1:4]
                       同時也配對S[1:F(F(9))] = S[1:F(4)] = S[1:2] ！！

有沒有清楚明白XD!? 好我假設有:p

那你可能會想 這個F函數有什麼鳥用呢= =?

就像老師上課說的因為當你把S跟T配對(T是pattern)時，
如果在某個時刻已經配對到"S中的i"跟"T中的j"也就是S[i-j+1:i] = T[1:j]
下一個要比對的就是S[i+1]跟T[j+1]是否相等？

如果相等的話很好i++, j++。
如果不相等呢？
    因為我們已經有T[1:j]的資訊了，所以不用再重新跑一次！

    因為我們知道S[i-j+1:i] = T[1:j]
                S[i-F(j)+1:i] = T[1:F(j)]
                S[i-F(F(j))+1:i] = T[1:F(F(j))]
                S[i-F(F(..j..))+1:i] = T[1:F(F(..j..))]

    所以我們可以直接把j變成F(j)

    也就是比較S[i+1] T[F(j)+1]是不是相等？

        如果相等的話很好i++, j=F(j)+1。（如果先做了j=F(j)那就只要j++就好了）
        如果不相等呢？
            這樣的情況跟上面最一開始的情況一樣了!!

總之就是一直做下去直到存在某個S[i+1] = T[F(F(..F(j)..))+1]

覺得符號很多頭昏眼花? 沒關係，讓我們來舉個例子。

        0        1         2
        1234567890123456789012
假設S = shikisfatabababahahaha
    T = abababab
        00123456 (T的F函式的值)

假設現在match情況是這樣 shikisfatababab ahahaha   S[10:15] =
                                 ababab ab        T[1:6]
                                                  其中i=15, j=6。

則繼續往下比對之後會變成shikisfatabababa hahaha   S[10:16] =
                                 abababa b        T[1:7]
                                                  其中i=16, j=7。
（因為S[16]==T[7]所以只要i++,j++就好了）


然後繼續往下比對        shikisfatabababa hahaha   S[10:16]
                                 abababa b        T[1:7]
但是因為S[17]!=T[8] 即'h'!='b'所以會變成
                        shikisfatabababa hahaha   S[12:16]
                                   ababa bab      T[1:F(7)] = T[1:5]
但是因為S[17]!=T[6] 所以變成
                        shikisfatabababa hahaha   S[14:16]
                                     aba babab    T[1:F(5)] = T[1:3]
但是因為S[17]!=T[4] 所以變成
                        shikisfatabababa hahaha   S[16:16]
                                       a bababab  T[1:F(3)] = T[1:1]
但是因為S[17]!=T[2] 所以變成
                        shikisfatabababa hahaha   S[17:16]
                                         abababab T[1:F(1)] = T[1:0]

有沒有點fu要怎麼用F來做比對了呢XDD?

那現在問題轉一下變成了 要如何求出F呢@@!?

我們可以利用一種類似遞推的方式

明顯的F(1) = 0
假設我們已經知道F(2) F(3) ... F(i-1) 那要怎麼求出F(i)呢?

其實仔細想一下的話 就會發現求出F的過程就ST匹配方式一樣哇!!

只是會變成T跟T自己做匹配而已:p

假設T = ababaabab

那麼一開始的話是
                T = a babaabab        i = 1
                      ababaabab       j = 0
因為T[i+1]!=T[j+1] 且 j=0 所以F(2) = 0

                T = ab abaabab        i = 2
                       ababaabab      j = 0
因為T[i+1]==T[j+1] 所以F(3) = j+1 = 1

                T = aba baabab        i = 3
                      a babaabab      j = 1
因為T[i+1]==T[j+1] 所以F(4) = j+1 = 2

                T = abab aabab        i = 4
                      ab abaabab      j = 2
因為T[i+1]==T[j+1] 所以F(5) = j+1 = 3

                T = ababa abab        i = 5
                      aba baabab      j = 3     不合，故j=F(j)
                T = ababa abab        i = 5
                        a babaabab    j = 1     不合，故j=F(j)
                T = ababa abab        i = 5
                          ababaabab   j = 0
因為T[i+1]==T[j+1] 所以F(6) = j+1 = 1

                T = ababaa bab
                         a babaabab
因為T[i+1]==T[j+1] 所以F(7) = j+1 = 2

                T = ababaab ab
                         ab abaabab
因為T[i+1]==T[j+1] 所以F(8) = j+1 = 3

                T = ababaaba b
                         aba baabab
因為T[i+1]==T[j+1] 所以F(9) = j+1 = 4

                T = ababaabab
                         abab aabab
                結束>w< ~~~~

因此就得到F函數的值了>w< 呀乎\(^o^)/

會求F函數的值也就同時會String Matching了!!!

不知道大家懂了沒=口=a

總之概念大概就這樣囉～～實踐方面就要自己動腦了XD"

---

不懂的還有不懂的話，這裡有我之前寫字串相關演算法的講義....雖然寫很爛啦= =|||
http://w.csie.org/~b99902112/NTUcourse/Chapter8-String.pdf

不然就再說吧XD" 看是問老師問助教還是....喵:p

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.140
推 gary810410:看懂了 感謝
推 shik:真不想推...|||
推 fei6409:胖胖郭超強的>w<
推 skyly:一年多過去了...說好的精美圖片呢...  怎麼還是手寫的 XDDD
推 poloo5582:我覺得一開始就教這個太超過了www
※ 編輯: math120908      來自: 118.160.236.217      (03/23 01:10)
推 OppOops:必推
推 garychou:大概懂了 不過shik被偷表還真可憐XD
推 garychou:借轉到我的個版3Q
推 mars90226:推~ 超強~
推 williamiced:推!不過我還是覺得好難QQ
推 ga800360:快推不然人家以為我看得懂...
推 q22554647:不能再同意樓上更多了QQ
推 yesjimmy62:推小小郭啦~~~
→ math120908:樓上電機卷哥!!
推 skyly:樓上上 soccer boy!!
推 chickending:大大講解得真好!!!天降甘霖啊~~~~