因为好像很多人还是不太懂，所以就尝试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)