实际上，在某些极端情况下，BF 算法性能会退化的比较严重，而 RK 算法需要用到哈希算法，但设计一个可以应对各种类型字符的哈希算法并不简单。对于工业级的软件开发来说，我们希望算法尽可能的高效，并且在极端情况下，性能也不要退化的太严重。而 BM（Boyer-Moore）算法就是一种非常高效的字符串匹配算法。

核心思想

我们把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。
image.png
在这个例子里，主串中的 c 在模式串中是不存在的，所以，模式串向后滑动的时候，只要 c 与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 c 的后面。
image.png
由现象找规律，当遇到不匹配的字符时，有什么固定的规律可以将模式串往后多滑动几位呢？BM 算法本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，就能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

原理分析

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来看，这两个规则分别都是怎么工作的。

1. 坏字符规则

之前在匹配字符时，我们是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯，而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。
image.png
我们从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。此处，c 就是坏字符。

模式串中不存在坏字符
我们拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符，也就是 c 与模式串中的任何字符都不匹配。此时我们可以将模式串直接往后滑动三位，将模式串滑动到 c 后面的位置，再从模式串的末尾字符开始比较。
image.png

模式串中存在匹配的坏字符
滑动以后，模式串中最后一个字符 d 还是无法跟主串中的 a 匹配。但因为，此时坏字符 a 在模式串中是存在的，模式串中下标为 0 的位置也是字符 a。所以在这种情况下，我们不能直接把模式串往后滑动三位，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。
image.png
第一次不匹配的时候，我们滑动了三位，第二次不匹配的时候，我们将模式串后移两位，那具体滑动多少位是怎么决定的呢？当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。
image.png
注意，如果坏字符在模式串里出现了多次，那我们在计算 xi 的时候，要选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

利用坏字符规则，BM 算法在最好情况下的时间复杂度是 O(n/m)。比如主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。不过只使用坏字符规则是不够的。因为根据 si-xi 计算出来的移动位数有可能是负数（下面会讲到为什么会是负数），比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还可能倒退。所以 BM 算法还需要用到好后缀规则。

2. 好后缀规则

好后缀规则实际上跟坏字符规则的思路是很类似的。当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。那此时该如何滑动模式串呢？当然，我们还可以利用坏字符规则来计算模式串的滑动位数，不过我们也可以使用好后缀处理规则。
image.png

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

如果在模式串中找不到了另一个相匹配的好后缀，怎么做？
如果在模式串中找不到另一个等于 {u} 的子串，我们就直接将模式串，滑动到主串中 {u} 的后面，因为之前的任何一次往后滑动，都没有匹配主串中 {u} 的情况。
image.png
其实，如果我们直接将模式串滑动到主串 {u}的后面的话，是会有一定风险的。如下图所示，bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串 {u*}，但如果我们将模式串移动到好后缀的后面，就会错过模式串和主串可以匹配的情况。
image.png
如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中，只要主串中的 {u} 与模式串有重合，那肯定就无法完全匹配，因为模式串中不存在 {u}。但当模式串滑动到前缀与主串中 {u} 的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。

如果好后缀的后缀与模式串的前缀相匹配，怎么办？
以上图为例，bc 是好后缀，且模式串中不存在可匹配的 {u}，那在模式串滑动过程中，只要模式串与主串重合的部分包含 {u}，那就肯定不能匹配。因为 bc 是好后缀，所以 {u} 的后缀只有一个 c。我们拿这个好后缀中的 c 去匹配模式串中的前缀，因为 {u} 的后缀只有一个字符，所以我们也只取模式串中的第一个字符，发现是相等的，所以这种情况下是有可能匹配的，所以我们移动模式串到 c 的位置。
image.png
*所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。

  • 后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。
  • 前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。

我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是 {v}，然后将模式串滑动到如图所示的位置，对应上面那个例子就是 c 的位置，{u} 是 bc，{v} 是 c。
image.png
当模式串和主串中的某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后滑动的位数？我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

实现思路

1. 坏字符规则实现思路

当遇到坏字符时，要计算往后移动的位数 si-xi，其中 si 是坏字符在模式串中的下标（从0开始），xi 是最靠右的匹配主串的坏字符在模式串中的下标。xi 的计算是重点，那如何查找主串中的坏字符在模式串中出现的位置呢？如果直接拿主串中的坏字符在模式串中顺序遍历查找，这样就会比较低效。但如果我们将模式串中的每个字符及其下标都存到散列表中，key为字符，value为下标，这样就能快速找到坏字符在模式串的位置下标了（经典的空间换时间策略）。

关于这个散列表，我们只实现一种最简单的情况，假设字符串的字符集不是很大，每个字符长度是 1 字节，我们用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。
image.png
如果将上面的过程翻译成代码，就是下面这个样子。其中，变量 b 是模式串，m 是模式串的长度，bc 表示刚刚讲的散列表。

  1. private static final int SIZE = 256;
  3. private void generateBC(char[] b, int m, int[] bc) {
  4.     for (int i = 0; i < SIZE; ++i) {
  5.         // 初始化bc
  6.         bc[i] = -1;
  7.     }
  8.     for (int i = 0; i < m; ++i) {
  9.         // 计算b[i]的ASCII值
  10.         bc[b[i]] = i;
  11.     }
  12. }

掌握了坏字符规则之后，我们先把 BM 算法代码的大框架写好，先不考虑好后缀规则，仅用坏字符规则，并且不考虑 si-xi 计算得到的移动位数可能会出现负数的情况。（因为哈希表记录的是不同字符在模式串中最后出现的位置，并不是 si 的位置往前查找的第一个位置，所以可能会出现 xi 大于 si 的情况。）

  1. public int bm(char[] a, int n, char[] b, int m) {
  2.     // 记录模式串中每个字符最后出现的位置
  3.     int[] bc = new int[SIZE];
  4.     // 构建坏字符哈希表
  5.     generateBC(b, m, bc);
  6.     // i表示主串与模式串对齐的第一个字符
  7.     int i = 0;
  8.     while (i <= n - m) {
  9.         int j;
  10.         // 模式串从后往前匹配
  11.         for (j = m - 1; j >= 0; --j) {
  12.             // 坏字符对应模式串中的下标是j
  13.             if (a[i+j] != b[j]) {
  14.                 break;
  15.             }
  16.         }
  17.         // 匹配成功，返回主串与模式串第一个匹配的字符的位置
  18.         if (j < 0) {
  19.             return i;
  20.         }
  21.         // 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
  22.         i = i + (j - bc[(int)a[i+j]]); 
  23.     }
  24.     return -1;
  25. }

image.png

2. 好后缀规则实现思路

好后缀规则的实现要比坏字符规则复杂一些，好后缀的处理规则中最核心的内容是：

  • 在模式串中，查找跟好后缀 {u} 匹配的另一个子串 {u*}
  • 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串 {v} 匹配的后缀子串

在不考虑效率的情况下，这两个操作都可以用暴力匹配查找的方式解决。那有没有更高效的方式来处理呢？因为好后缀也是模式串本身的后缀子串，所以，我们可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。

我们先来看，如何表示模式串中不同的后缀子串呢？因为后缀子串的最后一个字符的位置是固定的，下标为 m-1，我们只需要记录长度就可以了。通过长度，我们可以确定一个唯一的后缀子串。
image.png
现在，我们要引入最关键的变量 suffix 数组。suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀 {u} 相匹配的子串 {u*} 的起始下标值。
image.png
但是，如果模式串中有多个子串跟后缀子串 {u} 匹配，那 suffix 数组中该存储哪一个子串的起始位置呢？为了避免模式串往后滑动得过头了，我们肯定要存储模式串中最靠后的那个子串的起始位置，也就是下标最大的那个子串的起始位置。不过，这样处理就足够了吗？

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

如果我们只记录刚刚定义的 suffix，实际上，只能处理规则的前半部分，即在模式串中，查找跟好后缀匹配的另一个子串的位置。所以，除了 suffix 数组之外，我们还需要另外一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串。
image.png
现在，我们来看下，如何来计算并填充这两个数组的值？这个计算过程非常巧妙。

我们拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串求公共后缀子串。如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。
image.png
我们把 suffix 数组和 prefix 数组的计算过程，用代码实现出来，就是下面这个样子：

// 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;
        // 与b[0, m-1]求公共后缀子串
        while (j >= 0 && b[j] == b[m-1-k]) {
            --j;
            ++k;
            // j+1表示公共后缀子串在b[0, i]中的起始下标
            suffix[k] = j+1;
        }
        // 如果公共后缀子串也是模式串的前缀子串
        if (j == -1) {
            prefix[k] = true;
        }
    }
}

有了这两个数组之后，我们现在来看，在模式串跟主串匹配的过程中，遇到不能匹配的字符时，如何根据好后缀规则，计算模式串往后滑动的位数？

假设好后缀的长度是 k。我们先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k]等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则来处理。
image.png
好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k]等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。
image.png
如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 m 位。
image.png

代码实现

至此，好后缀规则的代码实现也讲完了。我们把好后缀规则加到前面的代码框架里，就可以得到 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);
    // j表示主串与模式串匹配的第一个字符
    int i = 0;
    while (i <= n - m) {
        int j;
        // 模式串从后往前匹配
        for (j = m - 1; j >= 0; --j) {
            // 坏字符对应模式串中的下标是j
            if (a[i+j] != b[j]) {
                break;
            }
        }
        // 匹配成功，返回主串与模式串第一个匹配的字符的位置
        if (j < 0) {
            return i;
        }
        int x = j - bc[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]) {
            return r;
        }
    }
    return m;
}