看板 b99902HW 關於我們 聯絡資訊
因為好像很多人還是不太懂,所以就嘗試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函數) 如果還是不懂 就我們一個一個來看@[email protected] 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函數其實就是KMP的精隨!! 假設上面例子:如果 上面叫實體字串 下面叫虛擬字串 那當我們在配對實體字串的時候 同時也在配對虛擬字串!! 意思就是我們在配對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:看懂了 感謝 03/22 20:41
shik:真不想推...||| 03/22 20:43
fei6409:胖胖郭超強的>w< 03/22 20:47
skyly:一年多過去了...說好的精美圖片呢... 怎麼還是手寫的 XDDD 03/22 21:11
poloo5582:我覺得一開始就教這個太超過了www 03/23 01:09
※ 編輯: math120908 來自: 118.160.236.217 (03/23 01:10)
OppOops:必推 03/23 01:31
garychou:大概懂了 不過shik被偷表還真可憐XD 03/23 03:41
garychou:借轉到我的個版3Q 03/23 03:54
mars90226:推~ 超強~ 03/23 13:07
williamiced:推!不過我還是覺得好難QQ 03/24 14:13
ga800360:快推不然人家以為我看得懂... 03/25 16:32
q22554647:不能再同意樓上更多了QQ 03/25 20:55
yesjimmy62:推小小郭啦~~~ 04/23 21:04
math120908:樓上電機卷哥!! 04/23 23:48
skyly:樓上上 soccer boy!! 04/25 23:00
chickending:大大講解得真好!!!天降甘霖啊~~~~ 05/15 00:27