关于KMP算法和BM算法的理解.docx

《关于KMP算法和BM算法的理解.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于KMP算法和BM算法的理解自己之前没有接触到模式匹配的问题。对于所谓的字符串匹配也只是简单的蛮力匹配。上周刚看了《多模式匹配算法及硬件实现》这篇文章。文章中主要讲的是多模式匹配算法：AC算法和WM算法以及这两个算法的改进。AC算法是基于KMP算法的，WM算法是基于BM算法的。只有充分理解了单模式匹配的KMP算法和BM算法才能理解多模式匹配算法，最后才能对模式匹配有一个深入的理解。下面主要说下自己对KMP算法和BM算法的理解。KMP算法和BM算法，它们分别是前缀匹配和后缀匹配的经典算法。所谓前缀匹配是指

2、：模式串和母串的比较从左到右，模式串的移动也是从左到右；所谓后缀匹配是指：模式串和母串的的比较从右到左，模式串的移动从左到右。看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同。KMP算法KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。KMP算法对于朴素匹配算法的改进是引入了一个跳转表next[]。但next[]刚接触时比较难于理解。next跳转表，在进行模式匹配，实现

3、模式串向后移动的过程中，发挥了重要作用。这个表看似神奇，实际从原理上讲并不复杂，对于模式串而言，其前缀字符串，有可能也是模式串中的非前缀子串，这个问题我称之为前缀包含问题。以模式串abcabcacab为例，其前缀abca，正好也是模式串的一个子串abc(abca)cab，所以当目标串与模式串执行匹配的过程中，如果直到第8个字符才匹配失败，同时也意味着目标串当前字符之前的4个字符，与模式串的前4个字符是相同的，所以当模式串向后移动的时候，可以直接将模式串的第5个字符与当前字符对齐，执行比较，这样就实现了模式

4、串一次性向前跳跃多个字符。这里只是一个模式串移动的思想。如何以较小的代价计算KMP算法中所用到的跳转表next，是算法的核心问题。这里我们引入一个概念f(j)，其含义是，对于模式串的第j个字符P[j]，f(j)是所有满足使P[1...k-1]=P[j-(k-1)...j-1](k

5、1从1到6递增，然后依次比较，直到找到最大值的k为止。但是这样的方法比较低效，而且没有充分利用到之前的计算结果。在我们处理P[8]='c'之前，P[7]='a'的最大前缀包含问题已经解决，f(7)=4，也就是说，P[4...6]=P[1...3]，此时我们可以比较P[7]与P[4]，如果P[4]=P[7]，对于P[8]而言，说明P[1...4]=P[4...7]，此时，f(8)=f(7)+1=5。再以P[9]为例，f(8)=5，P[1...4]=P[4...7]，但是P[8]!=P[5]，所以P[1...

6、5]!=P[4...8]，此时无法利用f(8)的值直接计算出f(9)。其实利用之前的结果，我们还可以得到更多的信息。还是以P[8]为例。f(8)=5，P[1...4]=P[4...7]，此时我们需要关注P[8]，如果P[8]!=P[5]，那么在匹配算法如果匹配到P[8]才失败，此时就可以将输入字符T[n]与P[f(8)]=P[5]对齐，再向后依次执行匹配，所以此时的next[8]=f(8)。而如果P[8]=P[5]，那么P[1...5]=P[4...8]，如果T[n]与P[8]匹配失败，那么同时也意味着T

7、[n-5...n]!=P[4...8]，那么将T[n]与P[5]对齐，T[n-5...n]也必然不等于P[1...5]，此时我们需要关注f(5)=2，这意味着P[1]=P[4]，因为P[1...4]=P[4...7]，所以P[4]=P[7]=P[1]，此时我们再来比较P[8]与P[2]，如果P[8]!=P[2]，就可以将T[n]与P[2]，然后比较二者是否相等，此时next[8]=next[5]=f(2)。如果P[8]=P[2]，那么还需要考察P[f(2)]，直到回溯到模式串头部为止。下面给出根据f(j)

8、值求next[j]的递推公式：如果P[j]!=P[f(j)]，next[j]=f(j);如果P[j]=P[f(j)]，next[j]=next[f(j)];当要求f(9)时，f(8)和next[8]已经可以得到，此时我们可以考察P[next[8]]，根据前面对于next值的计算方式，我们知道P[8]!=P[next[8]]。我们的目的是要找到P[9]的包含前缀，而P[8]!=P[5]，P[1...5]!=P[4...8]。我们