文章目录
-
-
- KMP算法基本原理
- 失效函数计算方法
- KMP算法复杂度分析
- 一些关键点
-
视频讲解：
KMP字符串匹配算法1_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
KMP算法基本原理
假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
还记得我们上一节讲到的好后缀和坏字符吗？这里类比一下，在模式串和主串匹配的过程中，把不能匹配的那个字符仍叫坏字符，把已经匹配的那段字符串叫作好前缀。
当遇到坏字符的时候，就要把模式串往后滑动，滑动过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。这个比较的过程能否更高效了呢？可以不用一个字符一个字符地比较了吗？
KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？
我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k(j为模式串中的下标)，i 不变，然后继续比较。
为了表述起来方便，把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。
如何求好前缀的最长可匹配前缀和后缀子串呢？这个问题不涉及主串，只需要通过模式串本身就能求解。所以，能不能事先计算好，在模式串和主串匹配的过程中，直接拿过来用呢？
类似 BM 算法中的 bc、suffix、prefix 数组，KMP 算法也可以提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为 next 数组，很多书中还给这个数组起了一个名字，叫失效函数（failure function），或者前缀表。
数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标。这句话有点拗口，我举了一个例子，你一看应该就懂了。
有了 next 数组，我们很容易就可以实现 KMP 算法了。我先假设 next 数组已经计算好了，先给出 KMP 算法的框架代码。
// a, b分别是主串和模式串；n, m分别是主串和模式串的长度。
public static int kmp(char[] a, int n, char[] b, int m) {
int[] next = getNexts(b, m);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && a[i] != b[j]) { // 一直找到a[i]和b[j]
j = next[j - 1] + 1;
}
if (a[i] == b[j]) {
++j;
}
if (j == m) { // 找到匹配模式串的了
return i - m + 1;
}
}
return -1;
}
简单匹配过程：
主串长度 n = 10, 模式串长度 m = 7
下标值： 0 1 2 3 4 5 6 7 8 9
主字串： a b a b a e a b a c
模式串： a b a b a c d
next数组：
下标值： 0 1 2 3 4 5
数组值： -1 -1 0 1 2 -1
i 为主串中的下标，j 为模式串中的下标
-
j = 0,i = 0: a[0] == b[0] ++j
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 1,i = 1: a[1] == b[1] ++j
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 2,i = 2: a[2] == b[2] ++j
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 3,i = 3: a[3] == b[3]
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 4,i = 4: a[4] == b[4]
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 5,i = 5: j = 5 > 0 && a[5] != b[5]
主字串： a b a b a e a b a c
模式串： a b a b a c d
j = next[j-1]+1 = next[5-1]+1 = 2+1 = 3
主字串： a b a b a e a b a c
模式串： ~ ~ a b a b a c d
j = 3 代表从模式串的第 j 位开始匹配，因为第 j 位之前的（
aba
）已经匹配好了。
…
简单解释一下：
- 对于主串，我们不重复访问字符，即每次比较都是从主串的的失效位（坏字符）开始的。比如上面的第一个坏字符是
e
e
- 在模式串中，0到 i 位的前缀找最大相同前后缀串位数是为了第 i+1 位失配时找模式串的匹配位 x ，假设从模式串的 x 位开始匹配，那么模式串的 0 到 x-1 位与主串的失配位（坏字符）往前数 x 位必须是一样的（比如上面的
aba
失效函数计算方法
next 数组（前缀表）是如何计算出来的？
当然，我们可以用非常笨的方法，比如要计算下面这个模式串 b 的 next[4]，我们就把 b[0, 4]的所有后缀子串，从长到短找出来，依次看看，是否能跟模式串的前缀子串匹配。很显然，这个方法也可以计算得到 next 数组，但是效率非常低。有没有更加高效的方法呢？
这里的处理非常有技巧，类似于动态规划。不过，动态规划我们在后面才会讲到，所以，我这里换种方法解释，也能让你听懂。
我们按照下标从小到大，依次计算 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]了。这个时候该怎么办呢？
我们假设 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]的最长可匹配后缀子串。
可是，如何求得 b[0, i-1]的次长可匹配后缀子串呢？次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串 b[0, y]。于是，查找 b[0, i-1]的次长可匹配后缀子串，这个问题就变成，查找 b[0, y]的最长匹配后缀子串的问题了。
按照这个思路，我们可以考察完所有的 b[0, i-1]的可匹配后缀子串 b[y, i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于 b[i]，那这个 b[y, i]就是 b[0, i]的最长可匹配后缀子串。
前面我已经给出 KMP 算法的框架代码了，现在我把这部分的代码也写出来了。这两部分代码合在一起，就是整个 KMP 算法的代码实现。
// b表示模式串，m表示模式串的长度
private static int[] getNexts(char[] b, int m) {
int[] next = new int[m];
next[0] = -1;
int k = -1;
for (int i = 1; i < m; ++i) {
while (k != -1 && b[k + 1] != b[i]) {
k = next[k];
}
if (b[k + 1] == b[i]) {
++k;
}
next[i] = k;
}
return next;
}
还是简单解释一下：
下标值： 0 1 2 3 4 5 6
模式串： a b a b a c d
next[] : -1 -1 0 1 2 -1 -1
当 i = 5：
此时
b[0, i-1]
为
ababa
，它有两个可匹配后缀子串：
- 第一个为
a
- 第二个为
aba
2
next[4] = 2
4
i-1 = 4,i = 5
现在
ababa
最长可匹配后缀子串(ababa)对应的模式串的前缀子串(ababa)的下一个字符(b)并不等于 b[i] (c)，那么我们就可以考察 b[0, i-1] (也就是
ababa
)的次长可匹配后缀子串 b[x, i-1] (ababa)对应的可匹配前缀子串 b[0, i-1-x] (ababa)的下一个字符 b[i-x] (ababa)是否等于 b[i] (c)。
- 如果等于，那 b[x, i]就是 b[0, i]的最长可匹配后缀子串;
- 如果不等，就按此逻辑（次次长可匹配后缀子串 ）再往前找
KMP算法复杂度分析
空间复杂度很容易分析，KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。
KMP 算法包含两部分，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。所以，时间复杂度要从这两部分来分析。
先来分析第一部分的时间复杂度：
计算 next 数组的代码中，第一层 for 循环中 i 从 1 到 m-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 增长的，那有没有可能让 j 不变呢？也没有可能。因为 next[j-1]的值肯定小于 j-1，所以 while 循环中的这条语句实际上也是在让 j 的值减少。而 j 总共增长的量都不会超过 n，那减少的量也不可能超过 n，所以 while 循环中的这条语句总的执行次数也不会超过 n，所以这部分的时间复杂度是 O(n)。
所以，综合两部分的时间复杂度，KMP 算法的时间复杂度就是 O(m+n)。
一些关键点
next数组计算代码里的：
k = next[k]
因为前一个的最长串的下一个字符不与最后一个相等，需要找前一个的次长串，问题就变成了求0到next(k)的最长串，如果下个字符与最后一个不等，继续求次长串，也就是下一个next(k)，直到找到，或者完全没有。
可以看这位博主的介绍：
如何更好地理解和掌握 KMP 算法? - 知乎
如何更好地理解和掌握 KMP 算法? - 知乎