算法教程精选算法基础 ACM/ICPC

字符串匹配算法（一）：BF算法和RK算法

yngcy2024-12-032024-12-03

一、前言

字符串（String）是由一系列字符组成的数据类型，用于表示文本。字符可以是字母、数字、符号或其他特殊字符。在编程语言中，字符串通常用引号（单引号或双引号）括起来。

无论是在算法题中，还是在项目开发中，字符串都十分常见。我们经常在字符串中查找某个字符串，如 Java 的 indexOf() 方法。查找方法底层依赖字符串匹配算法，字符串匹配问题也是字符串问题的一个重要分支。

二、什么是字符串匹配

2.1 定义

字符串匹配问题的定义如下：

给定字符串和字符串，其中也叫主串，字符串也叫模式串。在字符串中，找到的子串与相等。

我们要在主串中查找模式串，要满足主串长度大于模式串长度，否则就无法匹配。

2.2 分类

一般按照模式串的个数可以将字符串匹配问题分成两类：

单模式串匹配
多模式串匹配

单模式串匹配是指在主串中查找一个模式串的所有出现位置。而多模式串匹配是指在主串中同时查找多个模式串的所有出现位置。

常见的单模式串匹配算法有：

BF(Brute Force)算法：暴力匹配算法
RK(Rabin-Karp)算法：基于哈希的字符串匹配算法
KMP算法：利用部分匹配表进行快速匹配
BM算法：从模式串末尾开始匹配
Sunday算法：在BM算法基础上的改进算法

常见的多模式串匹配算法有:

AC自动机：基于Trie树实现的多模式串匹配算法
WM(Wu-Manber)算法：基于BM算法的多模式串匹配算法

本文将重点介绍BF算法和RK算法,它们是字符串匹配算法中最基础的两种算法。后续文章会介绍其他更高效的字符串匹配算法。

三、BF算法

BF 算法是暴力算法（Brute Force）的简称。它比较好理解，但是匹配效率不高。

它的核心思路是，模式串的长度是固定的，因此可以遍历主串，枚举子串的起始位置，即。然后截取长度为的子串，看是否有匹配的。

可以从上面的匹配过程中看出，每次匹配要匹配个字符，需要匹配次，因此 BF 算法的时间复杂度是。

四、RK算法

RK 算法全称是 Rabin-Karp 算法，它是基于哈希算法的暴力算法。前面的 BF 算法中，对比子串与模式串时依次比较每个字符，所以时间复杂度就比较高，为。

RK 算法的核心思路时在比较前计算子串的哈希值是否与模式串相等，如果相等则比较字符是否相等，否则就继续遍历。相当于在比较前设了一个“门槛”，只有过了“门槛”才会比较，省去了一些无用的比较，从而提高效率。

如果你不了解什么是哈希算法，也没关系，下面我来简单讲讲哈希算法。

我们知道函数映射，如这个函数，把映射到了上。而哈希函数的核心思想是把字符映射成值域更小、更容易比较的范围。如把映射成，把映射成等等。哈希函数所得出的值叫做哈希值，哈希函数的效率取决于计算哈希值的复杂度以及发生发生哈希冲突的概率，一个好的哈希算法是在尽可能短的时间内、并且发生冲突概率小。

现在我们来看看 RK 算法是如何设计哈希函数的。

假设字符集的大小为，这里的字符集约定了主串和模式串出现字符的范围。我们可以根据数位思想来计算字符串的哈希值，具体的，用一个进制数来表示一个字符串，然后将这个进制数转为十进制数作为哈希值，方便比较。

比如字符集是从 a ~ z 这 26 个小写字母，于是用 0 ~ 25 分别表示它们。例如计算“abc”的哈希值的过程如下：这种哈希算法有个特点，两个相邻子串的哈希值具有一定关系。两个相邻子串有交集，我们可以利用交集这部分快速计算下一个子串的哈希值。设子子串长度的长度为，有从上面式子可以得出，子串交集部分的值因为“错位”，后者是前者的倍。于是两个相邻子串的哈希值有如下关系：这里有个优化，可以预处理的幂，即、、……、，将结果存在长度为的数组中，然后通过下标访问对应的幂值。