# 字符串匹配

# BK 算法

BF 是 Brute Force 的缩写，中文叫作『 暴力匹配算法 』，也叫朴素匹配算法。

先定义两个概念，假如我们在字符串 A 中查找字符串 B：

• 字符串 A 就是『 主串 』
• 字符串 B 就是『 模式串 』
• 主串的长度记作 $n$，模式串的长度记作 $m$，并且 $n > m$。

BF 算法的思路很简单。在主串中，检查起始位置分别是 $0, 1, 2, ..., n-m$ 且长度为 $m$ 的个子串，看有没有跟模式串匹配的。

我们每次都比对 $m$ 个字符，要比对 $n-m+1$ 次，所以，这种算法的最坏情况时间复杂度是 $O(n*m)$。

虽然这种算法的时间复杂度很高，但是实际开发中却经常使用。原因有两点：

1. 实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 $m$ 个字符都比对一下。
2. 暴力匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 Bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。

# RK 算法

『 RK 算法 』的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。它其实就是刚刚讲的 BF 算法的升级版。

RK 算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。

因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

不过，通过哈希算法计算子串的哈希值的时候，我们需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高。有没有方法可以提高哈希算法计算子串哈希值的效率呢？

这就需要哈希算法设计的非常有技巧了。我们假设要匹配的字符串的字符集中只包含 $K$ 个字符，我们可以用一个 $K$ 进制数来表示一个子串，这个 $K$ 进制数转化成十进制数，作为子串的哈希值。

🌰 举例来说，比如要处理的字符串只包含 a ～ z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。我们把 a ～ z 这 26 个字符映射到 0 ～ 25 这 26 个数字。计算哈希的时候，我们只需要把进位从 10 改成 26 就可以。

相邻两个子串 s[i-1] 和 s[i]（ i 表示子串在主串中的起始位置，子串的长度都为 m ），对应的哈希值计算公式有交集，也就是说，利用一个公式，我们可以使用 s[i-1] 的哈希值很快的计算出 s[i] 的哈希值。

在上面这种情形中，公式可以为：

$h[i] = (h[i - 1] - S[i - 1] * 26^{m - 1}) * 26 + S[i + m - 1]$

为了提高 $26^{m-1}$ 这部分计算的效率，可以事先计算好 $26^0, 26^1, 26^2, ..., 26^{m-1}$，并且存储在一个长度为 $m$ 的数组中。当我们需要计算 $26$ 的 $x$ 次方的时候，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。

整个 RK 算法包含两部分：

1. 计算子串哈希值和模式串哈希值。
2. 子串哈希值之间的比较。

第一部分，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 $O(n)$。

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

# BM 算法

文本编辑器中的查找替换功能，用上一节讲的 BF 算法和 RK 算法，也可以实现这个功能，但是在某些极端情况下，BF 算法性能会退化的比较严重，而 RK 算法需要用到哈希算法，而设计一个可以应对各种类型字符的哈希算法并不简单。

『 BM 算法 Boyer-Moore 』它是一种非常高效的字符串匹配算法，但是原理比较复杂。

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

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

BM 算法的思想就是，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

# BM 算法原理分析

BM 算法的规则有两类，分别是：

• 坏字符规则（ bad character rule ）
• 好后缀规则（ good suffix shift ）

# 坏字符规则

之前讲的 BK 和 RK 算法，在匹配的过程中，我们都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。

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

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

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

这个时候，我们发现，模式串中最后一个字符 d，还是无法跟主串中的 a 匹配。坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。

当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。

• 如果坏字符在模式串里多处出现，那我们在计算 xi 的时候，选择最靠后的那个，最靠近 si 字符的那个。

( 注意，我这里说的下标，都是字符在模式串的下标 )

# 好后缀规则

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

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

如果在模式串中找不到另一个等于 {u} 的子串，要注意不可以直接将模式串滑动到主串中 {u} 的后面。因为可能出现好后缀的后缀子串，跟模式串的前缀子串匹配的情况。

我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是 {v}，然后将模式串滑动到如图所示的位置。

# BM 算法代码实现

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

# KMP 算法