32字符串匹配基础（中）：如何实现文本编辑器中的查找功能

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

文本编辑器中有查找替换功能，比如将Word中一个单词统一替换成另外一个。它是怎么实现的呢？上一节讲的 BF 算法在某些极端情况下，性能会退化的比较严重。RK 算法需要用到哈希算法，而设计一个可以应对各种类型字符的哈希算法并不简单。

那对于查找功能是重要功能的软件来说，它们的查找功能是用哪种算法实现的呢？实际上它是用BM（Boyer-Moore）算法实现的。它是非常高效的字符串匹配算法，性能是著名的KMP算法的3倍到4倍。

BM算法的核心思想

将模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。如下图所示：

在这个例子中，主串中的 c 在模式串中是并不存在的。所以模式串向后移动时，只要 c 与模式串有重合，肯定无法匹配。所以，可以一次性地把模式串往后多滑动几位，把模式串移动到 c 的后面。

由现象找规律，当遇到不匹配的字符时，有什么固定的规律，可以将模式串往后多滑动几位呢？这样一次性往后滑动好几位，那匹配的效率岂不是就提高了？

今天要讲的 BM 算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

BM 算法原理分析

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。

坏字符规则

前面算法匹配过程中，都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。而BM 算法匹配顺序比较特别，是按照模式串下标从大到小的顺序，倒着匹配的。如下所示：

从模式串的末尾往前倒着匹配时，若发现某个字符没法匹配时。把这个没有匹配的字符叫作坏字符（主串中的字符）。

如上所示，字符 c 与模式串中的任何字符都不可能匹配。这时可以将模式串直接往后滑动三位。

此时，坏字符 a 在模式串中是存在的，模式串中下标是0的位置也是字符 a。这时可以将模式串后移两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。

第一次匹配和第二次匹配移动的位数不一致，那么具体有什么规律呢？

当发生不匹配时，把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，则把这个坏字符在模式串中的下标记作 xi。如果不存在，则把 xi 记作-1，模式串往后移动的位数就等于 si - xi。（注意，这里的下标均为字符在模式串的下标）

如果坏字符在模式串里多处出现，则在计算 xi 时，选择最靠后的那个，这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是$O(n/m)$。比如，主串是aaabaaabaaabaaab，模式串是 aaaa。每次对比，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。

不过，单纯使用坏字符规则还是不够的。因为根据 si - xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。

好后缀规则

好后缀规则实际上跟坏字符规则的思路很类似。如下图所示，当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。

到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。

这个时候我们仍然可以利用坏字符规则来计算模式串的滑动位数。不过，也可以使用好后缀处理规则。这两种规则如何选择呢？首先看下好后缀规则是怎么工作的？

我们把已经匹配的 bc 叫做好后缀，记作{u}。拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那我们就将模式串滑动到子串{u*}与主串中{u}对齐的位置。

如果在模式串中找不到另一个等于{u}的子串，就直接将模式串滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。

不过，这种做法是不是有点太过头了呢？如下所示，这里 bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串{u*}，但是如果我们将模式串移动到好后缀的后面，可能错过模式串和主串可以匹配的情况。

如果好后缀在模式串中不存在可匹配的子串，那在一步一步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。

所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。

所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到如图所示的位置。

坏字符和好后缀的基本原理都讲完了，那么当模式串和主串中的某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后滑动的位数？

我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中的最大的，作为模式串往后滑动的位数。这还能避免前面提到的，根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

BM 算法代码实现

那么如何实现 BM 算法呢？

对于“坏字符规则”，当遇到坏字符时，要计算往后移动的位数 si-xi，其中 xi 的计算是重点，那么如何查找坏字符在模式串中出现的位置呢？如果拿坏字符在模式串中顺序遍历查找，会比较低效。这时可以使用散列表，将模式串中的每个字符及其下标都存到散列表中。这样就可以快速找到坏字符在模式串的位置下标了。

对于这个散列表，只看最简单的情况。假设字符串的字符集不是很大，每个字符长度是 1 字节，可以用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。

该过程对应的代码如下。其中，变量 b 是模式串，m 是模式串的长度，bc 表示刚刚讲的散列表。

private static final int SIZE = 256; // 全局变量或成员变量
private void generateBC(char[] b, int m, int[] bc) {
  for (int i = 0; i < SIZE; ++i) {
    bc[i] = -1; // 初始化bc
  }
  for (int i = 0; i < m; ++i) {
    int ascii = (int)b[i]; // 计算b[i]的ASCII值
    bc[ascii] = i;
  }
}

利用坏字符规则，首先将 BM 算法代码的大框架写好。先不考虑好后缀规则，仅用坏字符规则，并且不考虑 si-xi 计算得到的移动位数可能会出现负数的情况。

public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
  generateBC(b, m, bc); // 构建坏字符哈希表
  int i = 0; // i表示主串与模式串对齐的第一个字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    // 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
    i = i + (j - bc[(int)a[i+j]]); 
  }
  return -1;
}

代码对应的图如下所示：

接着，在实现好后缀时，先简单回顾下它对应的处理规则中的核心点：

在模式串中，查找跟好后缀匹配的另一个子串；若有多个，则取靠后的一个；
在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；

若不考虑效率的情况下，这两个操作都可以用很”暴力“的匹配查找方式解决。但是有没有一个高效的处理方式呢?

因为好后缀也是模式串本身的后缀子串，所以，可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。

首先，如何表示模式串中不同的后缀子串呢？因为后缀子串中最后一个字符的位置是固定的，下标为 m-1，所以只需要记录长度。通过长度，可以唯一确定一个后缀子串。

现在，引入最关键的变量 suffix 数组。suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。如下所示：

但是若模式串中有多个（大于1个）子串跟后缀子串{u}匹配，为了避免模式串往后滑动得过头了，要存储模式串中最靠后的那个子串的起始位置，也就是下标最大的那个子串的起始位置。

实际上，仅仅是选最靠后的子串片段来存储是不够的。好后缀规则：不仅要在模式串中，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能跟模式串前缀子串匹配的后缀子串。

上面的 suffix 数组只能处理规则的前半部分，也就是查找跟好后缀匹配的另一个子串。所以，我们还需要一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串。

那么如何来计算并填充这两个数组的值？拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。

对应的代码如下：

// b表示模式串，m表示长度，suffix，prefix数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
  for (int i = 0; i < m; ++i) { // 初始化
    suffix[i] = -1;
    prefix[i] = false;
  }
  for (int i = 0; i < m - 1; ++i) { // b[0, i]
    int j = i;
    int k = 0; // 公共后缀子串长度
    while (j >= 0 && b[j] == b[m-1-k]) { // 与b[0, m-1]求公共后缀子串
      --j;
      ++k;
      suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
    }
    if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
  }
}

接着来看，在模式串跟主串匹配的过程中，遇到不能匹配的字符时，如何根据好后缀规则，计算模式串往后滑动的位数？

假设好后缀的长度是 k。先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k]等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则来处理。

好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k]等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。

如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 m 位。

至此，好后缀规则的代码实现我们也讲完了。我们把好后缀规则加到前面的代码框架里，就可以得到 BM 算法的完整版代码实现。

// a,b表示主串和模式串；n，m表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
  generateBC(b, m, bc); // 构建坏字符哈希表
  int[] suffix = new int[m];
  boolean[] prefix = new boolean[m];
  generateGS(b, m, suffix, prefix);
  int i = 0; // j表示主串与模式串匹配的第一个字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    int x = j - bc[(int)a[i+j]];
    int y = 0;
    if (j < m-1) { // 如果有好后缀的话
      y = moveByGS(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
}

// j表示坏字符对应的模式串中的字符下标; m表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
  int k = m - 1 - j; // 好后缀长度
  if (suffix[k] != -1) return j - suffix[k] +1;
  for (int r = j+2; r <= m-1; ++r) {
    if (prefix[m-r] == true) {
      return r;
    }
  }
  return m;
}

BM 算法的性能分析及优化

对于 BM 算法的内存消耗。整个算法用到了额外的 3 个数组，其中 bc 数组的大小跟字符集大小有关，suffix 数组和 prefix 数组的大小跟模式串长度 m 有关。

如果我们处理字符集很大的字符串匹配问题，bc 数组对内存的消耗就会比较多。因为好后缀和坏字符规则是独立的，如果我们运行的环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则，这样就可以避免 bc 数组过多的内存消耗。不过，单纯使用好后缀规则的 BM 算法效率就会下降一些了。

对于时间复杂度来说。实际上前面的 BM 算法是个初级版本，有些复杂的优化并没有涉及到。基于我目前讲的版本，极端情况下，预处理计算 suffix 数组、prefix 数组的性能会比较差。

比如模式串是 aaaaaaa 这种包含很多重复的字符的模式串，预处理的时间复杂度就是 $O(m^2)$。当然，大部分情况下，时间复杂度不会这么差。关于如何优化这种极端情况下的时间复杂度退化，如果感兴趣，你可以自己研究一下。

实际上，BM 算法的时间复杂度分析起来是非常复杂的，这篇论文“A new proof of the linearity of the Boyer-Moore string searching algorithm”证明了在最坏情况下，BM 算法的比较次数上限是 5n。这篇论文“Tight bounds on the complexity of the Boyer-Moore string matching algorithm”证明了在最坏情况下，BM 算法的比较次数上限是 3n。

解答开篇 & 内容小结

对于BM 算法，尽管复杂、难懂，但匹配的效率很好。在实际的软件开发中，特别是一些文本编辑器中，应用比较多。

BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM 算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现 BM 算法。