一篇文章教你彻底理解用于字符串匹配的KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt三人同时发现，因此人们称它为Knuth-Morris-Pratt算法（简称KMP）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现依赖一个next()函数，函数本身包含了模式串的局部匹配信息，其时间复杂度为O(m+n)。
网上有很多文章讲解KMP算法，但都不够清晰透彻、通俗易懂，尤其在介绍最令人困惑的next()函数时，解释拗口，模棱两可，让读者理解起来颇为费劲。本人通过阅读各路大神的学习笔记，汲取其中精华部分，并结合自我理解，带你全面剖析KMP算法思想及实现，希望对学习KMP算法仍有盲区和疑惑的同学有所帮助。

KMP算法的原理

举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”（称为主串），我想知道，里面是否包含另一个字符串”ABCDABD”（称为模式串）？
1.首先，主串”BBC ABCDAB ABCDABCDABDE”的第一个字符与模式串”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以模式串需要后移一位。

2.因为B与A不匹配，模式串需要再往后移。

3.就这样，直到主串有一个字符，与模式串的第一个字符相同为止。

4.接着比较主串和模式串的下一个字符，发现还是相同。

5.直到主串有一个字符，与模式串对应的字符不相同为止，如下图所示。

6.这时，最自然的反应是，将模式串整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。

7.一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

8.怎么做到这一点呢？可以针对模式串，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

9.如下图所示，已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，”ABCDAB”中最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数：
　移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将模式串整体向后移动4位。
10.如下图，因为空格与Ｃ不匹配，模式串还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将模式串向后移2位。

11.如下图所示，因为空格与A不匹配，需要继续后移一位。

12.逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将模式串向后移动4位。

13.逐位比较，直到模式串的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将模式串向后移动7位，这里就不再重复了。

部分匹配表

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

-　"A"的前缀和后缀都为空集，共有元素的长度为0；
-　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
-  "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
-  "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
-  "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
-  "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
-  "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

按照定义，”ABCDAB”的部分匹配表即如下所示：

“部分匹配值”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。模式串移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

理解next数组

理解KMP算法的核心和难点就是理解next数组的巧妙设计，下面我会重点解释next数组的含义。
next数组，又叫做“失配函数”，它是以下标 0 开始的数组，为了方便大家理解，给出如下图示：

根据 KMP 算法，在失配位会调用该位的 next 数组的值，下面我将详细道出next数组的来龙去脉。

next[i]表示在失配位i之前的最长公共前后缀的长度。

首先，我们取之前已经匹配的部分（即蓝色的那部分！）

我们在上面说到“最长公共前后缀”，体现到下图所示的样子。

next数组的作用是通过寻找最长公共前后缀的部分，快速移动模式串，从而提高字符串匹配的效率，如下图所示：

next[i]返回当前位置i的最长公共前后缀的长度，假设为 len 。因为数组是由 0 开始的，所以 next 数组让模式串的第 len 位与主串匹配就是拿最长前缀之后的第 1 位与失配位重新匹配，避免匹配串从头开始，如下图所示。

如果上图中的红色位置依然匹配失效，则需要对上图中的绿色部分再次去求解它的最长公共前后缀长度（假设为len’），然后继续向右移动模式串，让模式串的第 len’ 位与主串的失配位重新进行匹配，如果仍旧不匹配，则继续以上过程操作。如下图所示：

我们发现，当发生失配的时候，可以借助递推的思想，根据已知的结果继续求出当前失配位之前的最长公共前后缀的长度，然后，继续移动模式串，从而进行新一轮的字符串匹配。

解释这么多，那么next数组究竟如何求出呢？

我们需要分两种情况考虑。

1.当红色部分相同（即S[k]==S[q]）时，则当前 next 数组的值为上一次 next 的值加一（即next[q] = k++），如上图所示。

2.当红色部分不等的时候，则需要对绿色部分递推求解 k’ = next[k-1]，然后再对新的 k’ 位置字符与 q 位置字符进行匹配，如果相等，则 next[q] = k’+1，否则，执行递推匹配，直到k’=0时递推结束。比如，模式串“ABCABXABCABC”，最后一个字符C的next数组值为3。（因为C之前的最长公共前后缀为“ABCAB”，而“ABCAB”的最长公共前后缀为“AB”，其长度为2，又源于第三个字符C与最后一个字符C匹配，所以最后一个字符C的next数组值为3）

代码实现

创建文件kmp.c，内容如下：

#include<stdio.h>
#include<string.h>

void makeNext(const char P[],int next[])
{    
    int q,k;    
    int m = strlen(P);
    next[0] = 0;    
    for (q = 1,k = 0; q < m; ++q)
    {        
        while(k > 0 && P[q] != P[k])
            k = next[k-1];        
        if (P[q] == P[k])
        {            
            // 上一次的next值+1
            k++;
        }
        next[q] = k;
    }
}
void kmp(const char T[],const char P[],int next[])
{    
    int n,m;    
    int i,q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);    
    for (i = 0,q = 0; i < n; ++i)
    {        
        while(q > 0 && P[q] != T[i])
            q = next[q-1];        
        if (P[q] == T[i])
        {
            q++;
        }        
        if (q == m)
        {
            q=0;            
            printf("Pattern occurs with shift: %d\n",(i-m+1));
        }
    }
}
int main()
{    
    int i;    
    int next[20]={0};    
    char T[] = "BBC ABCDABD ABCDABCDABDE";    
    char P[] = "ABCDABD";    
    printf("主串：%s\n",T);    
    printf("模式串：%s\n",P );    
    kmp(T,P,next);   
    printf("next数组：");    
    for (i = 0; i < strlen(P); ++i)
    {        
        printf("%d ",next[i]);
    }    
    printf("\n");    
    return 0;
}

保存后，在终端执行如下编译命令：

$ gcc -o kmp kmp.c
$ ./kmp
# 其运行结果如下：

主串：BBC ABCDABD ABCDABCDABDE
模式串：ABCDABD
Pattern occurs with shift: 4
Pattern occurs with shift: 16
next数组：0 0 0 0 1 2 0

总结

理解KMP算法的难点就在于理解next数组的实现，在遇到失配位时能够灵活地应用递推方法，根据已知的结果，进一步求解出子最长公共前后缀的长度，然后进一步的完成新一轮的匹配，从而避免从头开始，极大提高了匹配速率。kmp算法的时间复杂度O(n+m)，可以采用均摊分析来解答，具体可参考算法导论。

参考文章：
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 作者-阮一峰
http://www.tuicool.com/articles/e2Qbyyf