前面我们讲了 BM 算法，尽管它很复杂，也不好理解，但却是工程中非常常用的一种高效字符串匹配算法。有统计说，它是最高效、最常用的字符串匹配算法。不过，在所有的字符串匹配算法里，要说最知名的一种的话，那就非 KMP 算法莫属。实际上，KMP 算法跟 BM 算法的本质是一样的，下面就来分析下，如何借助 BM 算法的思路来更好地理解 KMP 算法？

基本原理

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。

KMP 算法的核心思想跟 BM 算法非常相近。我们假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符时，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。类比 BM 算法，在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。
image.png
与 BM 算法不同，模式串与主串的匹配过程是从模式串的首字符开始的，当遇到坏字符的时候，我们就要把模式串往后滑动。在滑动的过程中，只要模式串和好前缀有上下重合，那前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。那我们如何能对这一过程进行高效比较呢？
image.png
KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？

实际上，我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是 {v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。
image.png
为了表述方便，我们把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。
image.png

1. 如何求好前缀的最长可匹配前缀和后缀子串？

这个问题其实不涉及主串（因为好前缀是公共的），我们只需要通过模式串本身就能求解。所以，类比 BM 算法中的 bc、suffix、prefix 数组，KMP 算法也可以提前构建一个数组，用来存储模式串中的每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为 next 数组，很多书中还给这个数组起了一个名字，叫失效函数（failure function）。

数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可匹配前缀子串的结尾字符下标。具体示例如下图所示：
image.png
以模式串前缀 abab 为例，abab 的后缀子串有 bab、ab 和 b，其中，最长可匹配前缀子串为 ab，所以取 ab 子串的结尾字符 b 所在的下标索引 1，因此 next[3]=1。有了 next 数组，我们很容易就可以实现 KMP 算法了。假设 next 数组已经计算好了，先给出 KMP 算法的框架代码。

  1. /**
  2.  * a, b分别是主串和模式串；n, m分别是主串和模式串的长度
  3.  */
  4. public static int kmp(char[] a, int n, char[] b, int m) {
  5.     int[] next = getNexts(b, m);
  6.     int j = 0;
  7.     for (int i = 0; i < n; ++i) {
  8.         // 一直找到a[i]和b[j]
  9.         while (j > 0 && a[i] != b[j]) {
  10.             j = next[j - 1] + 1;
  11.         }
  12.         if (a[i] == b[j]) {
  13.             ++j;
  14.         }
  15.         // 找到匹配模式串的了
  16.         if (j == m) {
  17.             return i - m + 1;
  18.         }
  19.     }
  20.     return -1;
  21. }

2. 失效函数计算方法

现在，我们来看下最复杂的部分，也就是 next 数组是如何计算出来的？我们可以用暴力求解的方法，比如要计算模式串 b 的 next[4]，我们就把 b[0, 4] 的所有后缀子串从长到短找出来，依次看看，是否能跟模式串的前缀子串匹配。但显然，这种方法的效率非常低，那有没有更加高效的方法呢？
image.png
实际上，这里的处理技巧类似于动态规划。我们按照下标从小到大，依次计算 next 数组的值。当我们要计算 next[i] 的时候，前面的 next[0]，next[1] …… next[i-1] 应该已经计算出来了。利用已经计算出来的 next 值，我们就可以快速推导出 next[i] 的值了。

如果 next[i-1]=k-1，即子串 b[0, k-1] 是 b[0, i-1] 的最长可匹配前缀子串。如果子串 b[0, k-1] 的下一个字符 b[k] 与 b[0, i-1] 的下一个字符 b[i] 匹配，那子串 b[0, k] 就是 b[0, i] 的最长可匹配前缀子串。所以，next[i] 等于 k。但是，如果 b[0, k-1] 的下一字符 b[k] 跟 b[0, i-1] 的下一个字符 b[i] 不相等呢？这个时候就不能简单地通过 next[i-1] 得到 next[i] 了。这个时候该怎么办呢？
image.png
我们假设 b[0, i] 的最长可匹配后缀子串是 b[r, i]。如果我们把最后一个字符去掉，那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但不一定是最长可匹配后缀子串。所以，既然 b[0, i-1] 最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于 b[i]，那么我们就可以考察 b[0, i-1] 的次长可匹配后缀子串 b[x, i-1] 对应的可匹配前缀子串 b[0, i-1-x] 的下一个字符 b[i-x] 是否等于 b[i]。如果等于，那 b[x, i] 就是 b[0, i] 的最长可匹配后缀子串。
image.png
可是，如何求得 b[0, i-1] 的次长可匹配后缀子串呢？次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串 b[0, y]。于是，查找 b[0, i-1] 的次长可匹配后缀子串，这个问题就变成，查找 b[0, y] 的最长匹配后缀子串的问题了。
image.png
按照这个思路，我们可以考察完所有的 b[0, i-1] 的可匹配后缀子串 b[y, i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于 b[i]，那这个 b[y, i] 就是 b[0, i] 的最长可匹配后缀子串。

代码实现

  1. /**
  2.  * a, b分别是主串和模式串；n, m分别是主串和模式串的长度
  3.  */
  4. public static int kmp(char[] a, int n, char[] b, int m) {
  5.     int[] next = getNexts(b, m);
  6.     int j = 0;
  7.     for (int i = 0; i < n; ++i) {
  8.         // 一直找到a[i]和b[j]
  9.         while (j > 0 && a[i] != b[j]) {
  10.             j = next[j - 1] + 1;
  11.         }
  12.         if (a[i] == b[j]) {
  13.             ++j;
  14.         }
  15.         // 找到匹配模式串的了
  16.         if (j == m) {
  17.             return i - m + 1;
  18.         }
  19.     }
  20.     return -1;
  21. }
  24. // b表示模式串，m表示模式串的长度
  25. private static int[] getNexts(char[] b, int m) {
  26.     int[] next = new int[m];
  27.     next[0] = -1;
  28.     int k = -1;
  29.     for (int i = 1; i < m; ++i) {
  30.         while (k != -1 && b[k + 1] != b[i]) {
  31.             k = next[k];
  32.         }
  33.         if (b[k + 1] == b[i]) {
  34.             ++k;
  35.         }
  36.         next[i] = k;
  37.     }
  38.     return next;
  39. }

复杂度分析

1. 时间复杂度

KMP 算法包含两部分，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。所以，关于时间复杂度，我们要分别从这两部分来分析。

在第一部分计算 next 数组的代码中，第一层 for 循环中 i 从 1 到 m-1，for 循环内部还有一个 while 循环，如果我们能知道每次 for 循环、while 循环平均执行的次数，假设是 k，那时间复杂度就是 O(k*m)。但是，while 循环执行的次数不怎么好统计，所以我们放弃这种分析方法。我们可以找一些参照变量，i 和 k。i 从 1 开始一直增加到 m，而 k 并不是每次 for 循环都会增加，所以，k 累积增加的值肯定小于 m。而 while 循环里 k=next[k]，实际上是在减小 k 的值，k 累积都没有增加超过 m，所以 while 循环里面 k=next[k] 总的执行次数也不可能超过 m。因此，next 数组计算的时间复杂度是 O(m)。

在第二部分中，i 从 0 循环增长到 n-1，j 的增长量不可能超过 i，所以肯定小于 n。而 while 循环中的那条语句 j=next[j-1]+1 是不会让 j 增长的，因为 next[j-1] 的值肯定小于 j-1，所以 while 循环中的这条语句实际上也是在让 j 的值减少。而 j 总共增长的量都不会超过 n，那减少的量也不可能超过 n，所以 while 循环中的这条语句总的执行次数也不会超过 n，所以这部分的时间复杂度是 O(n)。

所以，综合两部分的时间复杂度，KMP 算法的时间复杂度就是 O(m+n)。

2. 空间复杂度

KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。