###引言###

之前看算法的时候，看到关于字符串匹配的 KMP算法，KMP算法总给人一种玄之又玄的感觉，地球人都说这个算法很难弄明白。我也觉得算法的设计和构思的确巧妙。导致给人理解上带来一定的难度。

但我觉得之所以理解上有困难,很大程度上是因为对算法知其然而不知其所以然。通常只是被动的去接受算法，但算法的具体思路和内部原理却没掌握。

网上的各种 KMP详解，KMP解析，KMP总结，KMP探索所说的我感觉都如出一辙。基本上没有清楚的解释算法为什么要这样构造和运行。并且算法这样设计之后对比原始算法带来了怎样的优化。也很多都没有讲。

下面是我结合自己的理解,写的一篇 KMP算法介绍，俗话说有多大碗，吃多大饭。算不上详解，也称不上探索，低调点当是浅析吧。

###变量定义###

先预定义几个变量，以便描述方便。 数组 des[N] 表示目标串 pat[M] 表示模式串, 数组下标从 1 开始, des[i…j] 表示从i到 j 的子串,pat[i…j] 类似。

对于原始算法而言。如果 des[i…i+j] 和 pat[1…j] 进行比对。设前面 j - 1 次比对都相同但第 j 次比对不同时,目标串回退 j - 1 位，接下来再继续拿 des[i+1] 和 pat[1] 进行重新比对。如此往复，直到比对完毕。但 KMP算法却几乎不需要像这样回退。而是利用之前 des[i…i+j] 和 pat[1…j] 的前 j-1 次正确匹配的数据。找到合适的回退位置。具体回到哪个位置。接下来进行讨论。

###next数组生成### 下面再引入next[M]数组了。因为KMP算法需要对模式串 pat[] 进行预处理。预处理的结果就放在 next[] 数组中。 next[i] 中存放的是 pat[1…i] 中前缀和后缀相同的最大长度,也就是 pat[1…next[i]] 既是 pat[1…i] 的前缀也是他的后缀。而且是满足条件最长的。

让我们举个例子进行介绍。假设模式串 ABAABAC 。注意这里的前缀和后缀都是子串。不含其本身。比如 ABC ， A 和 AB 都是允许的前缀但在 KMP中 ABC 是不算作前缀的。而 next[1] 对应于子串 A ，不包含他本身的前缀和后缀都不存在，所以 next[1] = 0，对于 next[2] 对应的子串是 AB ,不包含他本身的前缀有 A，但 A是不合要求的，因为没有一个后缀为 A。我们前面说了要有相同的前缀和后缀。所以 next[2] = 0。next[3] 对应子串 ABA 。前缀有 A 和 AB 。但只有 A 是符合要求的。因为 A 既是 ABA 的前缀也是 ABA 的后缀。因此 next[3] = 1; next[4] 对应于 ABAA。前缀有 A，AB，ABA,但只有前缀 A 是符合要求的。因为另外两个都不是他的后缀。next[5] 对应于 ABAAB。前缀有四个。其中 AB 是唯一符合要求的前缀，没有之一。next[6] 对应于 ABAABA 。总共五个前缀，其中 A 和 ABA都既是前缀也是后缀。但 ABA 的长度更长因此 next[6] = 3。ABAABAC 一种 6 个前缀但没一个亲生的。都不合要求。因此 next[7] = 0 至此应该知道对 next 有了一定的了解。

前面只是告诉了 next[] 中存储的内容,具体 next[] 数组怎么求。还没有说明。 KMP算法设计的目的就是为了让字符串匹配快速高效。那么对模式串的预处理肯定不能效率太低。

这里简要讲述一下处理的思想。有点动态规划的意思在里面。就是后面的处理结果要依赖或者说借助前面的处理结果。以达到高效的目的。

还是举 ABAABAC 的例子。next[1] 不用说是炮灰，肯定为 0 , next[1] = 0。对于i > 1，next[i] 要拿 next[i - 1] 之后的字符和第 i 个字符进行比对。也就是 pat[next[i - 1] + 1] 和 pat[i] 进行比对。为什么要拿第 next[i - 1] + 1 个字符和 pat[i] 进行比较呢？

因为 next[i - 1] 是符合 pat[1…i-1] 的最长前缀,同时他也是符合要求的最长后缀。所以如果 next[i - 1] + 1] 和 pat[i] 相同那么 next[i - 1] + 1 就是 pat[1…i] 的最长前缀了。为什么 next[i - 1] + 1 就是 pat[i…i] 的最长前缀呢？

反证法。假设 next[i] = k ( k > index[i - 1] + 1) 。那么 pat[1…i-1] 存在一个大于 index[i - 1] 的满足要求的子串既是前缀又是后缀，因为 pat[i…i] 满足既是前缀又是后缀的子串去除最后一个字符 pat[i] 之后也是 pat[1…i-1] 的前缀和后缀。而且这个既是前缀又是后缀的子串长度要比 next[i-1] 要大,为 k - 1。但因为我们已经计算出了 next[i - 1] 的值。但这里又得出一个比他更大的值。得出了矛盾。所以 next[i -1] + 1 是pat[1…i]满足要求的既是前缀也是后缀的子串。

当然这是比较理想的情况。但如果 pat[next[i - 1] + 1] 和 pat[i] 不相同怎么办呢? 这里的处理技巧是 next[] 预处理的核心。

这里我们要利用这样一个事实。那就是 pat[1…i] 满足要求的最长的既是前缀也是后缀的子串除去最后的那个字符 pat[i] 之后他也是 pat[1…i-1] 的前缀和后缀 (不一定是最长的) 。假设 pat[next[i - 1] + 1] 和 pat[i] 不相等。我们的算法就是从大到小遍历一遍 pat[1…i-1] 的所有既是前缀又是后缀的子串。并找到一个最长的符合要求的。这里符合要求是指,假设有 pat[1…i-1] 的既是前缀也是后缀的子串为 pat[1…k] , 如果 pat[k+1] == pat[i] 就是符合要求的。我们的目的就是要在所有这样符合要求的子串中找一个最长的。

我们知道 next[i-1] 是 pat[1…i-1] 的最长的既是前缀又是后缀的子串。次长的则是 next[next[i-1]] 。再次长则是 next[next[next[i-1]]] 。依次往复。为什么呢？

这里我们进行解释。首先 next[i-1] 是 pat[1…i-1] 最长的既是前缀又是后缀的子串这个毫无疑问。 next[] 就是这么定义的。但为什么次长就是 next[next[i-1]] 呢？因为首先 pat[1…i-1] 既是前缀又是后缀的次长子串的长度肯定小于 next[1…i-1] 。这里我们暂记 next[1…i-1] = t 。 pat[1…i-1] 的既是前缀又是后缀的子串肯定是 pat[1…t] 的前缀。同时因为 pat[1…i-1] 既是前缀又是后缀的次长子串是 pat[1…i-1] 的后缀。并且长度小于 t 。所以他肯定也是 pat[1…t] 的后缀。因为 pat[1…t] 是 pat[1…i-1] 的最长后缀 (这是因为 pat[1…t] 是 pat[1…i-1] 既是前缀又是后缀的最长子串）。所以 pat[1…i-1] 的次长子串既是 pat[1…t] 的前缀也是 pat[1…t] 的后缀。而 next[next[i-1]] 是满足要求的最长的。所以 next[next[i-1]] 就是 pat[1…i-1] 的次长子串。后面的依次类推。

因此我们要从大到小的遍历 pat[1…i-1] 的所有既是前缀又是后缀的子串。只需要按照上面的策略循环一遍。如 ABAABAC 的例子 next[4] 求 next[4] 首先拿 pat[next[3] + 1] 和 pat[4] 比对结果一个为 ‘B’ 一个为 ‘A’。然后拿 pat[next[1] + 1] 和 pat[4] 比对结果都为’A’。next[4] = next[1] + 1。具体的代码如下所示。(没有实测）

next[0] = -1;	//next[0]用于最后结束循环
int p = next[i - 1];
while (p >= 0 && pat[p + 1] != pat[i]) {
	p = next[p];
}
next[i] = p + 1;

至此我们已经讨论了next[]数组的生成过程。网上还有next[]生成的其他的写法。思想是一样的。这是我自己的写法。

###匹配策略###

我们假设next[]数组已经生成成功。下面进行匹配操作。

假设匹配过程进行到 des[i-j+1…i] 和 pat[1…j] ，其中 des[i-j+1…i-1] 和 pat[1…j-1] 都相等。但 des[i] 和 pat[j] 不等。那么肯定要进行回退。但怎么回退呢？

这里我们假设 j != 1。因为 j == 1 说明第一个都没有匹配成功。直接 des 的指针i右移一位，再继续比对。假设 j > 1 。KMP强大就在于她不需要回退 des 的 i 指针。但如果是原始算法是要回退 j - 1 个字符的。此时只需要对 j 进行回退。j = next[j - 1] + 1 。然后拿 des[i] 和 pat[j] 继续比对。为什么这样就行了呢？很多讲解 KMP的介绍都没有阐明这点。都是告诉大家就是要这样移动。导致大家不懂的还是不懂。第一个是不懂为什么不移动 i 。第二个是不懂为什么回退 j 到 next[j - 1] + 1 。

结合下图进行讲述。我们将 des[] 中的数组元素统一都用 x 表示，将 pat[] 中的数组元素统一都用 y 表示。

index	i-j+1, i-j+2, ..., i-j+k, ....,i-k,..., i-1, i
des		  x      x .....  x   .......   x ...... x   x
index	  1,     2, ...,  k,  ......,  j-k,..., j-1, j
pat		  y      y .....  y   .......   y  ......y   y

假设 next[j-1] = k 。则 pat[1…k] 和 pat[j-k…j-1] 分别为 pat[1…j-1] 的前缀和后缀。同理可以找到 des[i-j+1…i-1] 的前缀和后缀。

我们首先按照原始算法的方式将 i 回退。假设回退到 i-j+2 (i-j+2 < i-k) 。并且 j 也回退到 1 。然后开始匹配。这里可以负责任的告诉大家肯定是不会匹配成功的。为什么？

因为如果匹配成功那么说明 pat[1…j-2] 是和 des[i-j+2…i-1] 是相等的。但又因为根据前面的匹配我们知道 des[i-j+1…i-1] 是和 pat[1…j-1] 相等的。所以 pat[1…j-2] 既是 pat[1…j-1]的前缀又是他的后缀。这与 next[j-1] = k < j - 2 不符。

同理对于 i 回退到任何一个点 p < i - k 都不能正确匹配。因为如果匹配成功都会到一个同时是 pat[1…j-1] 的前缀和后缀的子串，并且长度为 i - p 。而这与 next[j-1] = k < i - p 不符。因此 i 不能回退到点 i-k 之前。

假设 i 回退到 i-k 的位置。 j 回退到 1 。 我们根据 next[j-1] = k 可知。 pat[j-k…j-1] 是 pat[1…i-1] 的前缀和后缀。因为 pat[1…k] 和 pat[j-k…j-1] 相同。而根据前面的匹配 pat[1…j-1] 和 des[i-j+1…i-1] 都是相同的。因此 des[i-k…i-1] 和 pat[j-k…j-1] 相同。因此 des[i-k…i-1] 也和 pat[1…k] 相同。因此如果 i 回退到 i-k 的位置，j 回到 1 的位置。我们可以断定接下来 k 次匹配肯定是成功的。

既然我们已经知道接下来 k 次匹配肯定是成功的。那我们就直接跳过这 k 次匹配。即 i 右移 k 位，从 i-k 移动到原先的位置。 j 右移 k 位移动到 k+1 的位置。最后的结果就是 i 的位置不变。而 j 移动到 k+1 的位置。这也就是前面所说的 j = next[j-1] + 1。至此 KMP的算法内部的运行机制基本已经讲述完毕。

应用前面的例子。当到第7个字符，无法匹配时。i不变。j回退到next[6] + 1，即第4个字符的位置。然后进行下一次匹配。

index	1 2 3 4 5 6 7 8 9 10
pat		A B A A B A C
des		A B A A B A A B A C

###结语###

具体的代码不列出来了。网上一大堆的代码。关键是算法的核心思想很少有介绍将其阐述清楚的。有的甚至只字不提。这是我个人对KMP算法的一点认识。 我觉得弄清算法的核心思想之后好像KMP也不是那么神秘。当然KMP算法的优秀那是毋庸置疑的。但好像其实也不是那么晦涩难懂。