kmp算法_joylnwang的专栏

你是否正在寻找关于kmp算法的内容？让我把最权威的东西奉献给你：

KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。但是相较于其他模式匹配算法，该算法晦涩难懂，第一次接触该算法的读者往往会看得一头雾水，主要原因是KMP算法在构造跳转表next过程中进行了多个层面的优化和抽象，使得KMP算法进行模式匹配的原理显得不那么直白。本文希望能够深入kmp算法，将该算法的各个细节彻底讲透，扫除读者对该算法的困扰。

kmp算法对于朴素匹配算法的改进是引入了一个跳转表next[]。以模式字符串abcabcacab为例，其跳转表为：

j 1 2 3 4 5 6 7 8 9 10

pattern[j] a b c a b c a c a b

next[j] 0 1 1 0 1 1 0 5 0 1

跳转表的用途是，当目标串target中的某个子部target[m...m(i-1)]与pattern串的前i个字符pattern[1...i]相匹配时，如果target[mi]与pattern[i1]匹配失败，程序不会像朴素匹配算法那样，将pattern[1]与target[m1]对其，然后由target[m1]向后逐一进行匹配，而是会将模式串向后移动i1 - next[i1]个字符，使得pattern[next[i1]]与target[mi]对齐，然后再由target[mi]向后与依次执行匹配。

举例说明，如下是使用上例的模式串对目标串执行匹配的步骤

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

b a b c b a b c a b c a a b c a b c a b c a c a b c

a b c a b c a c a b

a b c a b c a c a b

a b c a b c a c a b

a b c a b c a c a b

a b c a b c a c a b

a b c a b c a c a b

通过模式串的5次移动，完成了对目标串的模式匹配。这里以匹配的第3步为例，此时pattern串的第1个字母与target[6]对齐，从6向后依次匹配目标串，到target[13]时发现target[13]='a'，而pattern[8]='c'，匹配失败，此时next[8]=5，所以将模式串向后移动8-next[8] = 3个字符，将pattern[5]与target[13]对齐，然后由target[13]依次向后执行匹配操作。在整个匹配过程中，无论模式串如何向后滑动，目标串的输入字符都在不会回溯，直到找到模式串，或者遍历整个目标串都没有发现匹配模式为止。

next跳转表，在进行模式匹配，实现模式串向后移动的过程中，发挥了重要作用。这个表看神奇，实际从原理上讲并不复杂，对于模式串而言，其前缀字符串，有可能也是模式串中的非前缀子串，这个问题我称之为前缀包含问题。以模式串abcabcacab为例，其前缀4 abca，正好也是模式串的一个子串abc(abca)cab，所以当目标串与模式串执行匹配的过程中，如果直到第8个字符才匹配失败，同时也意味着目标串当前字符之前的4个字符，与模式串的前4个字符是相同的，所以当模式串向后移动的时候，可以直接将模式串的第5个字符与当前字符对齐，执行比较，这样就实现了模式串一次性向前跳跃多个字符。所以next表的关键就是解决模式串的前缀包含。当然为了保证程序的正确性，对于next表的，还有一些限制条件，后面会逐一说明。

如何以较小的代价计算kmp算法中所用到的跳转表next，是算法的核心问题。这里我们引入一个概念f(j)，其含义是，对于模式串的第j个字符pattern[j]，f(j)是所有满足使pattern[1...k-1] = pattern[j-(k-1)...j - 1](k < j)成立的k的最大。还是以模式串abcabcacab为例，当处理到pattern[8] = 'c'时，我们想找到'c'前面的k-1个字符，使得pattern[1...k-1] = pattern[8-(k-1)...7]，这里我们可以使用一个笨法，让k-1从1到6递增，然后依次比较，直到找到最大的k为止，比较过程如下

k-1 前缀 关系 子串

1 a == a

2 ab != ca

3 abc != bca

4 abca == abca

5 abcab != cabca

6 abcabc != bcabca

因为要取最大的k，所以k-1=1不是我们要找的结果，最后求出k的最大为41=5。但是这样的方法比较低效，而且没有充分利用到之前的计算结果。在我们处理pattern[8] = 'c'之前，pattern[7] = 'a'的最大前缀包含问题已经解决，f(7) = 4，也就是说，pattern[4...6] = pattern[1...3]，此时我们可以比较pattern[7]与pattern[4]，如果pattern[4]=pattern[7]，对于pattern[8]而言，说明pattern[1...4]=pattern[4...7]，此时，f(8) = f(7) 1 = 5。再以pattern[9]为例，f(8) = 5，pattern[1...4]=pattern[4...7]，但是pattern[8] != pattern[5]，所以pattern[1...5]!=pattern[4...8]，此时无法利用f(8)的直接计算出f(9)。

j 1 2 3 4 5 6 7 8 9 10

pattern[j] a b c a b c a c a b

next[j] 0 1 1 0 1 1 0 5 0 1

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-3601-1.html