KMP算法详解

这篇文章用于总结自己对KMP算法的一些理解，如有错误，请不吝指出。

KMP算法用于字符串匹配加快进程。

例如对于以下问题：

在字符串ABAACCABD中查找是否含有ABD这个串？

对于这个问题，很快就可以想到直接暴力搜索，多个循环依次匹配字符来达到目的，这种方法虽然简单易懂，但是效率很低。应用KMP算法可以有效地提高字符串匹配的效率。简单来说KMP算法是利用了已经匹配过的字符的信息来加快匹配的进程。例如

ABAACCABD

|  |  |

ABD

当检索到第三位时，A与D并不匹配，暴力算法会直接将字串从第二格开始重新检索，但是在KMP算法中会试图利用第一位的A与第二位的B互相已经匹配的信息来跳过一些不必要的步骤，已到达加速的目的。我个人认为实际上是利用了字符串中的回文（好像也不是），在详细解释KMP算法是如何利用这些信息加速之前，首先我们需要了解字符串前缀和后缀的概念。

对于任何一个字符串，我们可以提取出它的前缀和后缀，例如对于ABABC这个字符串

ABABC

前缀： ABAB，ABA,AB, A

后缀： BABC, ABC, BC, C

通过这个例子，相信不难看出前缀和后缀的规律，实际上类似于包含第一个/最后一个字符的字串。KMP算法实际上就是对最长公共前后缀的一个利用。公共前后缀就是指前缀和后缀中相等的一部分，例如：

ABAB

前缀: ABA,AB,A

后缀 BAB,AB,B

那么ABAB的最长公共前后缀就是AB，KMP算法的核心之一就是如何找到最长公共前后缀，这里先按下不讲，先解释如何利用最长公共前后缀来加快匹配的进程。

ABABAAAAACABABC

|  |  |  | ？

ABABC

对于这个两个字符串，公共前后缀已经标注成了红色，首先我们还是依次匹配，前面的ABAB都是完全相等的，知道第五位的A 与C不匹配，暴力算法会将ABABC向右移一位重新循环，从第一位开始继续匹配，KMP算法则会直接右移两位从第五位开始。（这里的第几位指的是主串中的位置）

ABABAAAAACABABC                                     

   |  

   ABABC

     暴力算法

ABABAAAAACABABC

           |  

     ABABC

     KMP算法

原因就在于在KMP算法中，我们已经得出了字串的公共前后缀AB，也就是在字串中一定存在一个前面AB = 后面的AB。在和主串匹配的过程中，因为ABABC中的ABAB部分是和主串中的前四位完全相等的，那么也就意味着主串之中也一定有一个前面AB=后面的AB，而实际上第一次匹配的过程中正式主串的前缀AB=字串的前缀AB，主串的后缀AB=字串的后缀AB。如下图所示：

ABABAAAAACABABC  

ABABC

KMP算法的做法就是，直接用字串的前缀AB去对主串的后缀AB

ABABAAAAACABABC  

     ABABC

因为字串的前缀AB=字串的后缀AB，字串的前缀AB又等于主串的前缀AB，那么显而易见字串的前缀AB也等于主串的后缀AB，而且由于我们已知它们相等，就不用从主串的第三位开始匹配，直接跳过后缀AB到主串的第五位A进行比较即可。我刚开始了解的其中一个疑惑时，这样跳不会漏掉中间的字符导致结果不对吗？这里我自己的想法是，实际上得出公共前后缀的过程已经排查了漏掉的情况，因为目的是去找完全相同的字符串，那么必须要保证所有的字符都相同，得到了最大的公共前后缀，也就意味着主串后面存在某一段字符串和字串中的前缀完全相同，当遇到不匹配的字符之后，只需要直接将字串的前缀挪到主串的后缀即可。（这段比较乱，随意看看即可）

接下来再看一个类似的例子，还是ABABC

ABACAAAAACABABC

|  |  | ?

BBABC

在这个例子中，第四位就已经不匹配了，我们应该根据ABA这个字符串的公共前后缀来计算，也就是A，那么只需要将ABABC挪到如下位置即可：

ABACAAAAACABABC

      | ?

      ABABC

那么对于我们想要查找的ABABC这个字符串，我们应该分别计算出它每一个字串的最长公共前后缀的长度即，

A 0

AB 0

ABA 1

ABAB 2

ABABC 0

我们把得到的这组数字成为最长长度表：

ABABC

0 01 20

根据这组数字，将在最前方插入-1就得到了Nxet数组用来指引字串的下一位置即

ABACAAAAACABABC

|  |  | ?

ABABC

-1001 2

当第四位的C与B不匹配时，Next数组的值为1，我们只需要将字串中的第一位（从第零位开始计算）移动C的位置即可，也就是

ABACAAAAACABABC

      | ?

      ABABC

      -100 1 2

然后C与B还是不匹配，根据Next数组，将第零位移动到这个位置。当Next数组等于-1时，直接将字串往后推一位。

ABACAAAAACABABC

        ?

        ABABC

       -100 1 2

以上就是KMP算法如何利用Next数组加速匹配过程，然后继续介绍如何在字串中求得Next数组。

对于任意一个我们想要搜寻的字符串，首先我们需要求得该字符串每个字串的最长公共前后缀长度的数组，并根据这个数组找出Next数组。任然举ABABC这个例子

ABABC

当我们求A的最长公共前后缀长度时，显而易见，应该是0，因为他没有任何字串，由此可以类推，所有字符串的长度数组L[0] = 0(用L表示长度数组，用N表示Next数组).

关键是如何求得任意一个L[K]的值，首先L[K]的值最多等于L[K-1]的值+1，因为在已知L[K-1]的最长公共前后缀长度，新加一个字符，那么最多就是直接相等，这种情况如下下图

ABAB？

已知ABAB的最长公共前后缀长度为2，即AB，当我们求ABAB?的公共前后缀时，只需要首先考虑前缀AB加上后面一位字符A是否等于后缀AB+后面一位字符？即ABA == AB？吗，如果此时？的位置是A，那么我们很快就可以得出ABABA的最长公共前后缀为3。以此类推当我们计算L[K]时首先比较L[K-1]的前缀+后一位字符是否等于L[K-1]的后缀+新的字符，如果相等L[K]=L[K-1]+1.这是最简单的一种情况。第二种情况就是不相等

ABAB?   如果此时?等于B，那么就不满足上述情况了，为了便于理解，我举一个更长的字符串当例子。

ABABABABB

对于这个字符串，不难看出他的前八位最长公共前后缀为ABAB，四位，现在我们要求第九位的最长公共前后缀长度。

ABABABAB？

为了便于理解，将前八位的前缀和后缀分别标注出来，此时当？= B那么不满足上述说的第一种情况，但是我们可以发现实际上第一种方法可以总结为 前缀+后一位字符是否 == 后缀+新字符，如果相等则长度+1就是结果。

ABABABAB？

即使不满足上述情况，因为前缀字符串等于后缀字符串，也就意味着前缀的前缀字符串，等于后缀的后缀字符串。如上图所示 红绿色AB表示前缀ABAB的前后缀，蓝黄色AB为后缀ABAB的前后缀，此时我们只需要再次验证红色前缀AB+后一位字符是否等于黄色前缀AB+新字符如果相等，那么第九位公共前后缀长度就应该等于ABAB的最长公共前后缀长度+1，如果不等，那么重复上述过程，直到前面的字符串公共前缀长度为0，那么所求的公共前后缀长度也等于0.回到举得第一个例子

ABAB？

如果？不等于A，那么则继续看前缀AB的公共前后缀，显而易见应该是0，那么ABAB？的公共前后缀长度就等于0. 最后在L数组的最前方插入-1就等于Next数组了。

以上是个人对于KMP算法一点总结，语言混乱，如有错误，请不吝指出。

本文为我原创本文禁止转载或摘编