【字符串匹配】KMP算法之道.docVIP

【字符串匹配】KMP算法之道 问题定义： 字符串匹配问题：T=“”，P=“daoluan”，问P是否在T中出现？答：是。 之前遇到的字符串匹配算法效率不是很看好，有限自动机之于最为朴素的穷举法有一定的提高，但是初始化过程仍不乐观，总体效率不高。奇葩的是，KMP算法初始化和匹配过程分别可以达到O(n)和O(m)，实在是神奇。本篇文章目的就是吃透KMP。 纵观KMP，它无非就基于三个核心的结论，吃透这个三个结论，将KMP踩在脚下。 KMP和有限自动机字符串匹配一样，借助了一个辅助一维表，但KMP的辅助表计算时间在O(m)内。这个辅助表是关于匹配内容P的前缀表。 在提及这些结论之前，先允许我啰嗦一下： 对于字串P，(k)P表示长度k的P的前缀；P(k)表示长度为k的P的后缀。比如P=abcdef，(3)P=abc，P(3)=def。 π(q)表示P的前缀(q)P的最长后缀(k)P的长度（也就是k要取最大值）。比如：P=ababababca，π(8)即(8)P=abababab的最长后缀(k)P的长度，k最大为6，因为 abababab|ca?ababab|abca π(8)=6。 上述的辅助表中元素i即为π(i)，比如： 匹配内容P=“daodaodaodaoluan”，那么关于P的前缀表即为：?P?d a o d a o d a o d a o l? u a n??π?0 0 0 1 2 3 4 5 6 7 8 9 0 0 0 0 π(q)有了定义，π*(q)可以有。通常加“*”表示所有，在这里也是。π*(q)是一个集合，它的所有成员可以迭代求出： π*(q)={k|(k)P是(q)P的后缀且kq} ={π1(q)，π2(q)，π3(q)，π4(q)....}，其中πn(q)=π[πn-1(q)]。 比如：同样对P=ababababca，求π(8)， 有下图结果（来自算法导论）： 所以π*(8)={0,2,4,6}。对于其他的q值也是这样计算。 假设已经得到了关于P的辅助表， 1 2 3 4 5 6 7 8 9 10 11 12 13 14 kmp() ????m = strlen(P) ????n = strlen(T) ????π[m] ????kmptab(π)??? //预处理辅助表 ????q = -1 ????for i=[0,n) ????????while q0 P[q+1]!=T[i] ????????????q = π[q] ????????if P[q+1]==T[i] ????????????q = q+1 ????????if q = m ????????????//??? 找到啦 ????????q = π[q]??? //继续剩余T的寻找 其中π[m]为辅助表。如果P[q]==T[i]能连续成立m次，那么可以找到T中的P。所以如果有辅助表的存在，匹配过程还是很容易理解的。 亮出三把秒杀KMP的“宝剑”，他们主要是用来计算辅助表的： π*(q)={k|(k)P是(q)P的后缀且kq}。 如果π(q)0，那么π(q)-1π*(q-1)。 若定义Eq-1={k|kq-1且(k)P是(q-1)P的后缀且P[k+1]=P[q]}。那么有：?π(q)=0???????????????????????????Eq-1是空集???????? =1+max(kEq-1)???Eq-1非空? 第一个结论可以通过“包含反包含”得出，用“显然”描述不为过吧:)。 第二个： π(q)=t，那么tq，所以π(q)-1=t-1q-1； π(q)=t，(t)P是(q)P的后缀，（去掉(t)P和(q)P的最后一个字符）那么(t-1)P同样也是(q-1)P的后缀； 根据结论一，得到t-1π*(q-1)，π(q)-1π*(q-1)总能成立。 第三个： 可以证明它，但是个人觉得图例更有助于我们理解，下图对第三个结论的理解很有帮助的，里面涉及了上面提到的定义，比如π等。? 上面的图中，前缀π(i-1)不断缩短，知道找到第i个字符和第【π(i-1)+1】个字符相等为止。 上面的基础就是为计算辅助表的。有了上面的结论： 1 2 3 4 5 6 7 8 9 10 11 kmptab(π) ????m = strlen(P) ????q = 0 ????π[0] = 0 ????for i=[1,m) ????????while q0 P[q]!=P[i] ????????????q = π[q]??? //??? 这里领悟到没有，跟第一个结论很有暧昧；同时，它跟第三个结论也有很大的渊源。 ? ????????if P[q]=P[i] ????????????q = q + 1??? //??