kmp算法_joylnwang的专栏(3)

利用跳转表实现字符串匹配的算法如下：

unsigned int KMP(const char* text, size_t text_length, const char* pattern, size_t pattern_length, unsigned int* matches) { unsigned int i, j, n; unsigned int next[pattern_length + 2]; BuildNext(pattern, pattern_length, next); i = 0; j = 1; n = 0; while(pattern_length + 1 - j <= text_length - i) { if(text[i] == pattern[j - 1]) { ++i; ++j; //发现匹配结果，将匹配子串的位置，加入结果 if(j == pattern_length + 1) { matches[n++] = i - pattern_length; j = next[j]; } } else { j = next[j]; if(j == 0) { ++i; ++j; } } } //返回发现的匹配数 return n; }

该算法在原有基础上进行了扩展，在原模式串末尾加入了一个“空字符”，“空字符”不等于任何的可输入字符，当目标串匹配至“空字符”时，说明已经在目标字符串中发现了模式，将模式串在目标串中的位置，加入matchs[]数组中，同时判定为匹配失败，并根据“空字符”的next，跳转到适当位置，这样算法就可以识别出字符串中所有的匹配子串。

最后，对kmp算法的正确性做一简要说明，还是以上文的模式串pattern和目标串target为例，假设已经匹配到第3部的位置，且在target[13]处发现匹配失败，我们如何决定模式串的滑动步数，来保证既要忽略不必要的多余比较，又不漏过可能的匹配呢？

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

target 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

pattern a b c a b c a c a b

对于例子中的情况，显然向后移动多于3个字符有可能会漏过target[9...18]这样的的可能匹配。但是为什么向后移动1个或者2个字符是不必要的多余比较呢？当target[13]与pattern[8]匹配失败时，同时也意味着，target[6...12] = pattern[1...7]，而next[8]=5，意味着，pattern[1...4] = pattern[4...7]，pattern[1...5] != pattern[3...7]，pattern[1...6] != pattern[2...7]，。如果我们将模式串后移1个字符，使pattern[7]与target[13]对齐，此时target[7...12]相当于pattern[2...7]，且target[7...12]与pattern[1..6]逐个对应，而我们已经知道pattern[1...6] != pattern[2...7]。所以不管target[13]是否等于pattern[7]，此次比较都必然失败。同理向前移动2个字符也是多余的比较。由此我们知道当在pattern[j]处发生匹配失败时，将当前输入字符与pattern[j]和pattern[next[j]]之间的任何一个字符对齐执行的匹配尝试都是必然失败的。这就说明，在模式串从目标串头移动到目标串末尾的过程中，除了跳过了必然失败的情况之外，没有漏掉任何一个可能匹配，所以kmp算法的正确性是有保证的。

后记：

首先要感谢Knuth-Morris-Pratt那篇光辉的论文《Fast Pattern Matching In Strings》，让我们在字符串处理的道路上看得更远。本文的例子和思路，均完全来自这篇论文，论文后面还对kmp算法的时间复杂度进行了彻底的分析。

KMP算法是一个高度优化的精妙算法，所以初涉该算法的时候，不要指望一蹴而就，一下子就将KMP算法理解透，而是应该循序渐进，逐步加深理解。据说该算法是Knuth，Morris，Pratt三人分别独立发现的，我斗胆揣测一下该算法的演进历程。首先应该是发现了模式串前缀的自包含问题，然后是提出了f(j)的概念，然后是搞定了如何计算f(j)，然后提出了next[j]的概念，然后搞定了如何用f(j)计算next[j1]，然后是只用f(j)做中间结果直接算出next[j1]。之所以我会这么猜测，主要是因为next跳转表的概念和生成算法太高端，中间经历了多个转换，极难一步到位想出来这么搞。所以我们也应该按照这个流程来学习kmp算法，而如何计算f(j)则是整个算法的精髓所在。

实际上，KMP算法中所用到的跳转表next是一个简化了的DFA，对于DFA而言，其跳转和输入的字符集有关，而KMP算法中的跳转表，对于模式串中的当前位置j-1，只有两种跳转方式pattern[j]，和^pattern[j]，所以kmp算法的跳转功能要弱于DFA，但是其构建速度，又大大快于DFA，在花费较小代价的同时，取得了近DFA的效果。下面是对于文中使用的模式串生成跳转表（上）和DFA的比较，显然DFA要复杂的多（这个是我手画的如果有画错的地方，请读者不吝赐教）。

以上就是关于kmp算法的全部内容，相信你一定会非常满意。

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