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
网友评论