前面我们介绍非常高效的 BM 算法，今天我们介绍另一个非常出名且高效的 KMP 算法。
KMP 算法思想
KMP 算法的思想和 BM 算法类似，都是希望可以在匹配失败之后多跳跃几次，避免不必要的匹配。
在 BM 算法中，我们使用了 坏字符 和 好后缀规则，在 KMP 算法中，我们使用好前缀规则实现跳跃：
KMP-好前缀规则.jpg
那么，好前缀该如何确定滑动范围呢？
首先我们要找到好前缀，在好前缀的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是 {v} ，长度是 k 。我们就可以把模式串一次性向后滑动 j-k 位。移动后继续比较。
KMP-滑动位数.jpg
为了表述方便，我把最长可匹配前缀子串的那个后缀子串，叫做最长可匹配后缀子串；对应的前缀子串，叫做最长可匹配前缀子串。
KMP-前后缀子串.jpg
你可能发现了，匹配的跳跃规则和主串无关，所以在模式串和主串进行匹配之前，我们可以预先对模式串进行预处理。
在预处理过程中，需要一个数组保存最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为 next数组，或者你可以称之为 失效函数 。
KMP-next数组.jpg
有了 这个数组，我们可以很容易地实现 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;
}
next 数组的计算方法
next 的数组可以用笨办法得到，比如要计算下面这个模式串 b 的 next[4]，我们把 b[0,4] 的所有后缀子串依次对比：
KMP-暴力求next数组.jpg
这样的效率很低，是否有更加高效的方法呢？
答案是肯定的，我们可以利用已经计算出来的 next 值，快速推导出后面的 next 值。
1.叠加相加
如果 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。
KMP-求next-递增.jpg
2.无法叠加，收缩范围
如果新加入的字符无法像之前那样方便地直接相加，那我们可以通过收缩范围看一看它能否让一个稍小的前后缀重叠：
KMP-求next-回缩.jpg
解释一下这个图：x 代表后缀子串逐渐向后方收缩，相应的，前缀子串也会向前收缩，当某个时刻 b[i] == b[i-x] 的时候，说明 next 可以在 b[x] ~ b[i-1] 的子串上进行叠加。
3.收缩范围的等价问题
我们知道，只有在后缀子串和前缀子串相同的时候，才可以进行叠加操作。所以，在收缩范围的时候，我们可以将后缀子串的收缩看作前缀子串的收缩。同时，一个子串是否是可匹配前缀子串，我们可以通过之前已经求得的 next 数组很容易地计算出来。
KMP-求next-回缩简化.jpg
next 的构建：
1.如果 b[0，i-1] 的最长前缀与下一个字符 b[i] 相等，则 next[i] = next[i-1] +1
2.如果不相等，我们需要收缩查找范围。其中，后缀向右侧收缩 等价于 前缀向左侧收缩，所以我们可以将问题简化成为前缀收缩。
3.收缩的前缀子串是否是可匹配前缀子串呢？我们可以借助之前的 next 数组快速判断。
代码如下：
// 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;
}
性能分析
- 空间复杂度：我们需要 next 数组保存信息，next 大小为 m。所以空间复杂度为O(m)。
- 时间复杂度：程序主要分成两个部分，第一部分是构建 next 数组，第二部分是借助 next 进行匹配。
在第一部分中，程序在 for 循环中运行 m 次，在 while 循环中只会减小 k ，而 k 的增加量最多不过是 m（k 增加由 if 中的 ++k 提供），所以 while 循环次数不会超过 m，故第一部分的，时间复杂度为 O(m)。
第二部分中，程序在 for 循环中运行 n 次，在 while 循环中只会减小 j ，而 j 的增加量最多是 n （增加由 if 中的 ++j 提供），所以，while循环次数不会超过 n ，故第二部分的时间复杂度为 O(n)。
两部分复杂度相加，KMP 算法的时间复杂度为 O(m+n)。
代码实现
根据上面的思想，我自己实现了 KMP 算法，可以用于参考：
def kmp(a, b):
'''
实现KMP算法
:param a: 主串
:param b: 模式串
:return: 位置列表
'''
res = []
n = _next(b) # 构建模式串的 next 数组
for i in range(len(a) - len(b) + 1): # i -> 将作为和 b 对比的基础下标，即 a[i] 将和 b[0] 比较。
j = 0 # j-> 作为模式串的比对进度的下标
x = 0 # x-> 作为主串的比对进度的下标
while j < len(b): # 没有比对完全
if a[i + x] == b[j]: # 如果当前字符串相同，就比对下一个字符
x += 1
j += 1
else: # 如果字符串不同，我们根据好前缀规则进行跳跃
k = n[j] # k->最大可匹配前缀的最后一个字符的下标
move = j - k # move->跳跃步数
i += move # 跳跃
break
if j == len(b): # 匹配完成,执行下面的语句后就会跳出循环
res.append(i)
return res
def _next(b):
'''
构建 next 数组
:param b: 模式串
:return: next 数组
'''
n = [-1 for i in range(len(b))] # 初始化
k = -1
for i in range(1, len(b)): # 遍历b
while k != -1 and b[k + 1] != b[i]: # 当下一个字符和可匹配前缀的下一个字符不符，进行收缩
k = n[k]
if b[k + 1] == b[i]: # 当字符匹配，k + 1
k += 1
n[i] = k # 记录
print(n)
return n
if __name__ == '__main__':
a = 'aacbccaaabcaa'
b = 'aaabcaa'
r = kmp(a, b)
print(r)
以上就是 KMP 算法的全部内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论