因為好像很多人還是不太懂，所以就嘗試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 ※ 編輯: math120908 來自: 118.160.236.217 (03/23 01:10)