【数据结构与算法】之字符串匹配算法之 BF、RK、BM --- 第十八篇

冷不防 2022-03-22 11:46 178阅读 0赞

本文为极客时间《数据结构与算法之美》专栏的学习笔记。

## **本文目录：** ##

**1、BF 算法**

**2、RK 算法**

**3、BM 算法**

3.1  BM 算法的核心思想

3.2  BM 算法原理分析

3.2.1  坏字符规则

3.2.2  好后缀规则

3.2.4  BM 算法代码实现

3.2.5  BM 算法的性能分析及优化

**4、总结**

--------------------

本文主要讲述字符串匹配常用的几种算法，它们分别是：BF 算法、RK 算法、BM 算法。

# 1、BF 算法 #

BF 算法中的 BF 是 Brute  Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。这种算法简单好懂，但是相应的性能也不高。

**主串和模式串的关系：**

> 比方说：我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以：n > m。

** BF 算法的思想：**

> **我们在主串中，检查起始位置分别是 0、1、2 ... n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

从上面的算法思想和例子，我们可以看出，在极端情况下，比如：主串是“aaaa....aaaaaaa”，模式串是“aaaaab”。我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是：O(n\*m)。

尽管理论上，BF 算法的时间复杂度很高，是 O(n\*m)，但在实际的开发中，它却是一个比较常用的字符串匹配算法。主要原因有两点：

第一，实际的软件开发中，**大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以停止了，不需要把 m 个字符都比对一下。**所以，尽管理论上的最坏情况时间复杂度是 O(n\*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。

第二，BF算法思想简单，代码实现也简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这就是我们常说的 [KISS（Keep  it  Simple  and  Stupid）设计原则][KISS_Keep_ it_ Simple_ and_ Stupid]。

--------------------

# 2、RK 算法 #

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Krap 的名字来命名的。这个算法理解起来也不难。个人感觉就是 BF 算法的升级版。

RK 算法的思想：

> **通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（暂不考虑哈希冲突）。因为哈希值是一个数字，数字之间的比较是否相等是非常快速的，所以模式串和主串中的子串之间的比较效率就会提高了。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

不过，通过哈希算法计算子串的哈希值的时候，需要遍历子串中的每个字符。尽管模式串与子串之间的比较效率提高了，但是，算法整体的效率并没有提高。这就需要设计出一个有技巧的哈希算法了：

假设要匹配的字符串的字符集中只包含 K 个字符，可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。举例说明：

比如：要处理的字符串只包含 a~z 这 26 个小写字母，那么我们就用二十六进制来表示一个字符串。把 a~z 这 26 个字符映射到 0~25 这 26 个数字，a 表示 0，b 表示 1，以此类推，z 表示 25。

二十六进制的计算方法和十进制是相似的，在进位的时候把 10 换成 26 即可：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2][]**二十六进制的哈希算法**

我们上面用二十六进制数来表示一个字符串，对应的哈希值就是二十六进制数转化成十进制的结果。

这种哈希算法有一个特点，在主串中，相邻的两个子串的哈希值的计算是有一定关系的。举例说明：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3][]

规律：相邻两个子串 s\[i-1\] 和 s\[i\]（i 表示在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，即：可以使用 s\[i-1\] 的哈希值很快计算出 s\[i\] 的哈希值。如果用公式表示的话，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4][]

这里有一个小细节需要注意：那就是 26^(m-1) 这部分的计算，可以通过查表得方法来提高效率。可以事先计算好 26^0、26^1、26^2 …… 26^(m-1)，并且存储在一个长度为 m 得数组中，公式中得“次方”就对应数组得下标。当我们需要计算 26 得 x 次方得时候，就可以从数组得下标为 x 的位置取值，直接使用，省去了计算的时间。

![20190128152816116.png][]

下面就来分析下 RK 算法的时间复杂度是多少？

整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，可以通过设计特殊的哈希算法，只要扫描一遍主串就能计算出所有子串的哈希值，这部分的时间复杂度为 O(n)。

模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，**RK 算法整体的时间复杂度就是 O(n)**。

讲到这里，基本的 RK 思想已经解释清楚了。但是我们还需要考虑两个问题：

1、如果模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机整型数据可以表示的范围，该如何解决呢？

2、散列冲突。上面我们设计的哈希算法是没有散列冲突的，因为，一个字符与一个二十六进制数一 一对应，不同的字符串的哈希值肯定不同（因为是基于进制来表示一个字符串的）。

实际上，我们**为了能将哈希值落在整数型数据范围内，可以牺牲下，允许哈希冲突**，这个哈希算法又该如何设计呢？

哈希算法的设计方法有很多。这里举一个例子说明下：

假设字符串中只包含 a~z 这 26 个英文字母，那么我们每个字母对应一个数字，比如 a 对应 1，b 对应 2 …… z 对应 26。我们可以把字符串中每个字母对应的数字相加，最后得到的和作为哈希值。这种哈希算法产生的哈希值的数据范围就相对小多了。当然这只是一个例子，你也可以将每一个字母对应一个素数，而不是 1，2，3…… 这样的自然数，这样冲突的概率就会降低一些。

那么新的问题就出现了：**存在哈希冲突的时候，有可能子串和模式串的哈希值虽然是相同的，但两者本身并不匹配。**

解决散列冲突：当我们发现一个子串的哈希值跟模式串的哈希值相等的时候，只需要再对比一下子串和模式串本身就好了。当然，如果子串的哈希值与模式串的哈希值不相等，那对应的子串和模式串肯定也是不匹配的，就不需要比对子串和模式串本身了。

所以，哈希算法的冲突概率要相对控制的低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要对比子串和模式串本身，那时间复杂度就会退化成 O(n\*m)。但也不需要太悲观，一般情况下，冲突不会很多，RK 算法的效率还是比 BF 算法高的。

--------------------

# 3、BM 算法 #

**文本编辑器中的查找和替换功能是如何实现的呢？**

如果用上面的 BF 算法和 RK 算法，也可以实现这个功能，但是在某些极端的情况下，BF 算法性能就会退化的比较严重，而 RK 算法需要用到哈希算法，而设计一个可以应对各种类型字符的哈希算法并不简单。

对于工业级的软件来说，希望算法尽可能的高效，并且在极端的情况下，性能也不要退化的太严重。那么，**对于查找功能是重要功能的软件来说，比如一些文本编辑器，它们的查找功能都是用哪种算法来实现的呢？有没有比 BF 算法和 RK 算法更加高效的字符串匹配算法呢？**

本部分要讲解的 BM（Boyer-Moore） 算法，是一种非常高效的字符串匹配算法。据实验统计，它的性能是著名的 KMP 算法的 3 到 4 倍。但是 BM 算法的原理比较复杂，可能不那么容易学习。

## 3.1  BM 算法的核心思想  ##

把模式串和主串的匹配过程看作是模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是：模式串往后移动一位，然后从模式串的第一个字符开始重新匹配。下面，举例进行说明：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 5][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 6][]

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

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

## 3.2  BM 算法原理分析 ##

**BM 算法包含两个部分，分别是：坏字符规则和好后缀规则。**

### 3.2.1  坏字符规则  ###

前面的 BF 算法和 RK 算法，在匹配的过程中，我们都是按模式串的下标从小到大的顺序，依次与主串的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 7][]

而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 8][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 9][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 10][]

这个时候，模式串中最后一个字符是 d，还是无法与主串中的 a 匹配，这个时候，还能将模式串往后滑动三位吗？

答案是：不行的。因为这个时候，坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 11][]

第一次不匹配的时候，滑动了三位，第二次不匹配的时候，将模式串往后滑动了两位，那具体滑动多少位，有没有什么规律呢？

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 12][]

需要说明的是，如果坏字符在模式串中多处出现，则计算 xi 的时候，选择最靠后的那个。避免让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

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

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

### 3.2.2  好后缀规则 ###

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 13][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 14][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 15][]

不过，当模式串中不存在等于 \{u\} 的子串时，我们直接将模式串滑动到主串 \{u\} 的后面。这样做是否有点太过头了呢？

再来看下面的例子：这里面 bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串 \{u\*\}，但是如果我们将模式串移动到好后缀的后面，如果所示，那就会错过模式串和主串可以匹配的情况。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 16][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 17][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 18][]

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

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

### 3.2.4  BM 算法代码实现 ###

先看“坏字符规则”：当需要坏字符时，要计算往后移动的位数 si-xi，其中 xi 是计算的重点，即，**如何找到坏字符在模式串中出现的位置呢？**

如果我们拿坏字符在模式串中顺序遍历查找，这样就会比较低效，势必影响这个算法的性能。这时，散列表就可以派上用场了，可以将模式串中的每个字符及其下标都存在散列表中。这样就可以快速找到坏字符在模式串的位置下标了。

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 19][]

将上面的过程翻译成代码。其中，变量 b 是模式串，m 是模式串的长度，bc 表示散列表。

// 全局变量
    private static final int SIZE = 256;
    
    /**
    * @param b：模式串
    * @param m：模式串的长度
    * @param bc：散列表
    */
    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) {
    		// 计算 b[i]的 ASCII 值
    		int ascii = (int)b[i];
    		// 将下标i存储到散列表中下标为b[i]散列值的位置
    		bc[ascii] = i;
    	}
    }

掌握了坏字符规则之后，先把 BM 算法代码的大框架写好，先不考虑好后缀规则，仅用坏字符规则，并且不考虑 si-xi 计算得到的移动位数可能为负的情况：

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

下图展示了上面代码的过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 20][]

至此，已经实现了包含坏字符规则的框架代码，只剩下往框架代码中填充好后缀规则了。

再回顾下，好后缀的处理规则的核心内容：

> 1、在模式串中，查找跟好后缀匹配的另一个子串；
> 
> 2、在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串。

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 21][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 22][]

但是，在模式串中可能会出现多个子串跟后缀子串 \{u\} 匹配，上面已经讲过，为了避免模式串往后滑动得过头了，取最后（即下标最大）的那个子串的起始位置。

但是光这样处理还不够。我们不仅要在模式串中，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能跟模式串前缀子串匹配的后缀子串。

如果我们只记录刚刚定义的 suffix，实际上，只能处理规则的前半部分，即：在模式串中查找跟好后缀匹配的另一个子串。所以，除了 suffix 数组之外，我们**还需要另外一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串。**（所以模式串的后缀子串的开头字符就必须和模式串的开头字符相同）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 23][]

现在，我们考虑下：**如何来计算并填充这两个数组的值？**

我们拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k ，那我们就记录 suffix\[k\] = j（j 表示公共后缀子串的起始下标）。如果 j 等于0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix\[k\] = true。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 24][]

suffix 数组和 prefix 数组的计算过程实现代码如下：

/**
     * @param b：模式串
     * @param m：模式串的长度
     * @param suffix
     * @param 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;
    	}
    	
    	// b[0,i]
    	for (int i = 0; i < m - 1; i++) {
    		int j = i;
    		int k = 0;   // 公共后缀子串长度
    		while(j >= 0 && b[j] == b[m - 1 - k]){
    			// 与b[0,m-1]求公共后缀子串
    			--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，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则来处理。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 25][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 26][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 27][]

至此，好后缀规则的代码实现我们也讲完了。我们把好后缀规则加到前面的代码框架里，就可以得到 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;
    }

### 3.2.5  BM 算法的性能分析及优化 ###

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

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

对于执行效率来说，我们可先从时间复杂度的角度来分析。实际上，我前面讲的 BM 算法是个初级版本。为了让你能更容易理解，有些复杂的优化我没有讲。基于我目前讲的这个版本，在极端情况下，预处理计算 suffix数组、prefix 数组的性能会比较差。

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

--------------------

# 4、总结 #

1、BF 算法是最简单、粗暴的字符串匹配算法，它的实现思路是：拿模式串与主串中所有子串匹配，看是否有能匹配的子串。所以，时间复杂度也较高，是O(n\*m)，n 和 m 分别表示主串和模式串的长度。不过在实际的软件开发中，因为这种算法实现简单，对于处理小规模的字符串匹配很好用。

2、RK 算法是借助哈希算法对 BF 算法进行改造的，即对每个子串分别求哈希值，然后拿子串的哈希值与模式串中哈希值比较，减少了比较的时间。所以，理想情况下， RK 算法的时间复杂度是 O(n)，跟 BF 算法相比，效率提高了很多。不过这样的效率取决于哈希算法的设计算法，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化为 O(n\*m)。

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220322/47e1b665f9a24c9a80d04162fd45cd0c.png
[KISS_Keep_ it_ Simple_ and_ Stupid]: https://baike.so.com/doc/5460245-5698634.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220322/c80a725a0244442d965154c5cb363d95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2]: /images/20220322/4ccb89514be64a6193db40660e566488.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3]: /images/20220322/91ee2b7c9a2443a3b3e70fb62490c48f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4]: /images/20220322/c2dcd8e689084699bc1be23c0fcb751e.png
[20190128152816116.png]: /images/20220322/f913aa154d664b07acce93777036c78b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 5]: /images/20220322/4ef218b2282f4a1e886e6e8ae282a675.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 6]: /images/20220322/4a094cbd1c44423582fad07c571d8802.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 7]: /images/20220322/816454702fbd4139bfb981dd2e2d4a8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 8]: /images/20220322/c6f47f0bb0d94157812cce437c4f712c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 9]: /images/20220322/a45776409795481891582ef2d3cf3db9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 10]: /images/20220322/39e4e5b5da064d2e8d77dcd9e0c8c43c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 11]: /images/20220322/47cbd7055f41421981ffb202d6f09dba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 12]: /images/20220322/d6db1c3e125347d0b4b58475f63b26e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 13]: /images/20220322/958c50e3e6aa46b4aa5e3a58c17c2d38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 14]: /images/20220322/8aa9a689f1ee4c51a19a725fd763468e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 15]: /images/20220322/9c22d0e6ab4f4c9d94d33d328d2a62f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 16]: /images/20220322/5bd791bed907487a8c566868e545d2d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 17]: /images/20220322/32375e713fc94fe0aa7774b9fcc1660f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 18]: /images/20220322/d630688325e54ed9a8ca5832fb436114.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 19]: /images/20220322/c1d62e14b2404cd2bd5a0f70b43026b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 20]: /images/20220322/b819f3176d9f4f158c9727eeb00d5644.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 21]: /images/20220322/7cf007c7f79c4ae1b462e64a0a724228.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 22]: /images/20220322/501b604cc7d846d49431fc246dc076ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 23]: /images/20220322/770ae7638e234561b6b472f3aa2b569b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 24]: /images/20220322/64386dde7f774e68b7fb174fa48565a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 25]: /images/20220322/a9e1ca744f434c5fa2d9abb866a81e6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 26]: /images/20220322/a2968f8e12464d059483d867b83f083a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 27]: /images/20220322/beeaf6959a274269ade3c32acb006ffc.png