KMP 算法
- 参考资料
- 正文
  - 部分匹配表
    - 最优前缀
    - 最优后缀

KMP 算法

参考资料

本文参考算法导论，清华大学出版社的数据结构C语言版，伯乐在线的我理解的KMP算法，matrix67大神的博客，再根据自己理解写下这篇文章

正文

KMP算法是解决字符串匹配问题，详细来说，是当前有A，B两个字符串，KMP算法就是来判断B串是否是A串子串的高效算法。比如你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？” 相对于朴素的时间复杂度为O(mn)的比较算法（虽然在大多是情况下只有O(m+n) 但在这里我们只考虑最坏情况）KMP算法稳定在O(m+n) ，因此有较广泛的应用。 KMP算法是我遇到的第一个看了算法导论和网上一些资料后还有些懵懂的算法，后来发现其实主要原因是我们上数据结构这门课时老师讲的不是很清楚，所以有些关键的东西一直没有弄清。

出于对Matrix67大神的崇拜，直接引用他的例子说事。当前有两个字符串A=”abababaababacb”，B=”ababacb”，首先看看朴素算法是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。刚开始我们先从i=j=1开始比较，当我们发现i=j=5时，A和B的下一个字符就不相等了。

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

那么此时我们就要把i倒退回i=2，j倒退回j=1重新开始比较。

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
  B = a b a b a c b
  j = 1 2 3 4 5 6 7

因此当我们遇到像A= “aaaaaaaaaaaaaaaaaaaaaaaaaab”，B=”aaaaaaaab”这样的字符串时，传统朴素算法每次匹配错误后B串只前进一格的做法就显得很慢。 KMP算法高效解决了字符串匹配中不断回退的问题，也就是上面例子中i从5倒退回2的问题。KMP算法的想法是相对于之前一次匹配不成功子串前进一格，能不能子串一次前进多个格子。在提出解决方案前，我们首先引入一些概念：

部分匹配表

下面这个是“ababacb”这个模板的部分匹配表：

index:	1	2	3	4	5	6	7
char:	a	b	a	b	a	c	b
value:	0	0	1	2	3	0	0

如果我有一个7个字符的模板（这里我们就用“ababacb”来举例子），我的部分匹配表将会有7格。如果此时此刻我正匹配模板的第7格即最后一格，那意味着我匹配了整个模板（“ababacb”）；如果我正匹配模板的第6格，则意味着当前仅匹配了整个模板的前6位（“ababac”），此时第7位(“b”)是无关的，不用去管它；目前我还没有提到部分匹配表每格数据的含义，在这里仅仅是交代了大概。

现在，为了说明刚刚提到的每格数据的含义，我们首先要明白什么是最优前缀什么是最优后缀。

最优前缀

一个字符串中，去除一个或多个尾部的字符所得的新字符串就是最优前缀。例如 “S”、 “Sn”、 “Sna”、 “Snap”都是“Snape”的最优前缀。

最优后缀

一个字符串中，去除一个或多个首部的字符所得的新字符串就是最优后缀。例如“agrid”、 “grid”、“rid”、 “id”、“d”都是 “Hagrid”的最优后缀。

有了两个概念，我现在可以用一句话来概括部分匹配表里每列数据的含义了：

模板（子模板）中，既是最优前缀也是最优后缀的最长字符串的长度。

下面我举例说明一下这句话。我们来看部分匹配表的第3格数据，如果你还记得我在前面提到的，这意味着我们目前仅仅关心前3个字母（“aba”）。在“aba”这个子模板中，有两个最优前缀（“a”和“ab”）和两个最优后缀（“a”和“ba”）。其中，最优前缀“ab”并不是最优后缀。因此，最优前缀与最优后缀中，相同的只有“a”。那么，此时此刻既是最优前缀也是最优后缀的最长字符串的长度就是1了。

我们再来试试第4格，我们应该是关注于前4个字母（“abab”）。可以看出，有3个最优前缀（“a”、“ab”、 “aba”）和3个最优后缀（“b”、“ab”、“bab”）。这一次 “ab” 既是最优前缀也是最优后缀，并且长度为2，因此，部分匹配表的第4格值为2。

这是很有趣的例子，我们再看看第5格的情况，也就是考虑“ababa”。我们有4个最优前缀（“a”、 “ab”、“aba”，和“abab”）和4个最优后缀（“a”、 “ba”、“aba”，和“baba”）。现在，有两个匹配“a”和“aba” 既是最优前缀也是最优后缀，而“aba”比“a”要长，所以部分匹配表的第5格值为3。

看看第6格的情况，不难看出，这两个集合之间不会有任何的交集。因为，所有最优后缀都以“c”结尾，但没有任何最优前缀是以“c”结尾的，所以没有相匹配的，因此第7格值为0。

当我们找到了部分匹配的字符串时，可以用部分匹配表里的值来跳过前面一些字符（而不是重复进行没有必要的比较）。具体是这样工作的：当i=j=5时，i的值保持不变，j=3，然后继续比较。当i=7，j=5时发现下一组又不相等了，此时i保持不变，j=3，然后又开始比较。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好）。那么如何得知j该等于多少呢，现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]!=B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。

我们看一看当 i=j=5时的情况。

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

此时，A[6]!=B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j’。j’可能是多少呢？仔细想一下，我们发现，j’必须要使得B[1..j]中的头j’个字母和末j’个字母完全相等（这样j变成了j’后才能继续保持i和j的性质）。这个j’当然要越大越好。而这恰好是部分匹配表的性质，即我们要找既是最优前缀又是最优后缀的最长字符串。在这里，B [1..5]=”ababa”，”aba”就是我们想要的，于是j=next[j]。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了 4：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
      B = a b a b a c b
      j = 1 2 3 4 5 6 7

ps：代码不想写，上其他博客找吧。