数据结构精品课件-KMP算法.pptVIP

参考：/blog/yaochunnian/7059486 /c-cloud/p/3224788.html KMP算法 回顾BF算法 第一趟 第二趟 第三趟 第四趟 对BF模式匹配的一种改进算法。 由D.E.Knuth、J.H.Morris和V.R.Pratt同时发现，简称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。 其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的‘部分匹配’的结果将模式向右‘滑动’尽可能远的一段距离后，继续进行比较。 第一趟 第二趟 KMP算法来由分析（1） 如果： T0 T1 T2… Tj-2 ≠ T1 T2… Tj-2Tj-1 则： T0 T1 T2… Tj-2 ≠ Si-j+1…Si-2Si-1 那么下一趟匹配就可以跳过去。 S0S1S2…Si-j-1Si-jSi-j+1…Si-2Si-1Si T0 T1 … Tj-2 Tj-1Tj S0S1S2…Si-j-1Si-jSi-j+1…Si-2Si-1Si T0 T1 … Tj-2 Tj-1Tj 同理，如果：T0 T1 T2… Tj-3 ≠ T2… Tj-2Tj-1 则： T0 T1 T2… Tj-3 ≠ Si-j+2…Si-2Si-1 那么下下一趟匹配也可以跳过去。 KMP算法来由分析（2） 依此类推，跳到什么时候结束呢？ 直到对于某一个“k”值， T0 T1 T2… Tk ≠ Tj-k-1 Tj-k…Tj-2Tj-1 但：T0 T1 T2… Tk-1 = Tj-k Tj-k +1… Tj-2Tj-1 则： T0 T1 T2… Tk-1 = Si-kSi-k+1…Si-2Si-1 从这趟开始继续匹配，模式串相当于向右滑i-k个位置。 KMP算法来由分析（3） S0S1S2…Si-j-1Si-jSi-j+1…Si-kSi-k+1Si-k+2…Si-2Si-1Si T0 T1 … Tj-k Tj-k+1 Tj-2 Tj-1Tj k到底应该是多少？ KMP算法来由分析（4） 可见，一旦si和tj比较不相等，主串s的指针不一定要回朔，主串si（或si+1）可直接与tk（0=k〈j）比较，k的决定与主串s并无关系，而只与模式串t本身的构成有关，即从模式串t本身就可求出k值。 讨论一般情况，设s=“s0s1...sn-1”，t=“t0t1...tm-1”。假定： 模式串的子串“t0t1...tk-1”已和主串 “si-ksi-k+1...si-1”匹配，下一次可直接比较si和tk； k个 k个 k个 k个 在si≠tj处失配，如果此时的模式串t 则必有： 所以 next[j]如下： 其它情况 当j=0时 由此定义可推出next的函数值： j 0 1 2 3 4 5 6 7 模式串 next[j] a b a a b c a c -1 0 0 1 1 2 0 1 next[j]是模式串中第j个字符与主串中相应字符“失配”时，在模式串中需要重新和主串中该字符进行比较的字符的位置。 可以用递推的方法推出next的值。当j＝０时，next[j]=-1;设next[j]=k，即t中存在 其中k为满足等式的最大值。以下求next[j+1]，分两种情况讨论： 1、若tk=tj，则表明模式串t中有： 因此next[j+1] = next[j]+1 = k+1; 那么我们应该利用已经得到的next[0]···next[j]来求t[0]···t[k-1]这个子串中最大相同前后缀，可能有同学要问了——为什么要求t[0]···t[k-1]的最大相同前后缀呢 原因在于t[k]已经和t[j]失配了，而且 t[0] ···t[k-1] = t[j-k] ···?t[j-1] 也就是说t[0]···t[k-1]这么长的子串是用不了了，我们希望找个t[0]…t[x]=t[j-x-1]…p[j-1]，但x是多少呢？头大啊。 又因为只是在t[k]≠ t[j]处失配的，因此 t[k-1]=t[j-1] t[k-2]=t[j-2] … t[k-x]=t[j-x] t[k-x-1]=t[j-x-1] 即在t[0]..t[k-1]中寻找最大相同前后缀。 t[0]…t[x-1]t[x]t[x+1]…t[k-x]…t[k-1]t[