字符串匹配 - KMP算法

前面我们介绍非常高效的 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的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间