《数据结构与算法之美》-5-字符串匹配

算法 预处理时间 匹配时间
BF算法 / 朴素算法 0 (无需预处理) Θ(nm)
Rabin-Karp算法 Θ(m) 平均 Θ(n + m),最差 Θ((n-m)m)
基于有限状态机的搜索 Θ(mk) Θ(n)
克努斯-莫里斯-普拉特算法 Θ(m) Θ(n)
Boyer-Moore字符串搜索算法 Θ(m + k) 最好Ω(n/m),最坏 O(n)
Bitap算法 Θ(m + k) O(mn)

BF算法

BF算法 中的 BFBrute Force 的缩写,中文叫作 暴力匹配算法,也叫 朴素匹配算法。从名字可以看出,这种算法的字符串匹配方式很“暴力”,当然也就会比较简单、好懂,但相应的性能也不高。

  • 主串
  • 模式串

把主串的长度记作 n,模式串的长度记作 m

在主串中查找模式串,所以 n>m

BF算法的思想:

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

尽管理论上,BF算法的时间复杂度很高,是O(n*m),但在实际的开发中,它却是一个比较常用的字符串匹配算法。为什么这么说呢?原因有两点。

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

第二,朴素字符串匹配算法思想简单,代码实现也非常简单。简单意味着不容易出错,如果有bug也容易暴露和修复。在工程中,在满足性能要求的前提下,简单是首选。这也是我们常说的 KISS(Keep it Simple and Stupid) 设计原则。

所以,在实际的软件开发中,绝大部分情况下,朴素的字符串匹配算法就够用了。

RK算法

RK算法的全称叫 Rabin-Karp算法,是由它的两位发明者 RabinKarp 的名字来命名的。

通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了(这里先不考虑哈希冲突的问题,后面我们会讲到)。因为哈希值是一个数字,数字之间比较是否相等是非常快速的,所以模式串和子串比较的效率就提高了。

通过查表的方法来提高效率。

BM算法1

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

一次性把模式串往后多滑动几位,把模式串移动到c的后面。

BM算法原理分析

坏字符规则(bad character rule)

没有匹配的字符叫作坏字符(主串中的字符)。

好后缀规则(good suffix shift)

BM算法代码实现

1
2
3
4
5
6
7
8
9
10
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计算得到的移动位数可能会出现负数的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

引入最关键的变量 suffix数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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]中的起始下标
}
i
if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
}
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 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;
}

KMP算法基本原理

KMP算法是根据三位作者(D.E.Knuth,J.H.Morris和V.R.Pratt)的名字来命名的,算法的全称是Knuth Morris Pratt算法,简称为KMP算法。

KMP算法的核心思想,跟上一节讲的BM算法非常相近。我们假设主串是a,模式串是b。在模式串与主串匹配的过程中,当遇到不可匹配的字符的时候,我们希望找到一些规律,可以将模式串往后多滑动几位,跳过那些肯定不会匹配的情况。

这里我们可以类比一下,在模式串和主串匹配的过程中,把不能匹配的那个字符仍然叫作 坏字符,把已经匹配的那段字符串叫作 好前缀

好前缀的所有后缀子串中,最长的可匹配前缀子串的那个后缀子串,叫作最长可匹配后缀子串;对应的前缀子串,叫作最长可匹配前缀子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// a, b分别是主串和模式串;n, m分别是主串和模式串的长度。
public static int kmp(char[] a, int n, char[] b, int m) {
int[] next = getNexts(b, m);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && a[i] != b[j]) { // 一直找到a[i]和b[j]
j = next[j - 1] + 1;
}
if (a[i] == b[j]) {
++j;
}
if (j == m) { // 找到匹配模式串的了
return i - m + 1;
}
}
return -1;
}

失效函数计算方法

小结

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

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

BM算法 尽管复杂、难懂,但匹配的效率却很高,在实际的软件开发中,特别是一些文本编辑器中,应用比较多。如果一遍看不懂的话,你就多看几遍。

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

BM算法有两个规则,坏字符和好后缀。KMP算法借鉴BM算法的思想,可以总结成好前缀规则。这里面最难懂的就是next数组的计算。如果用最笨的方法来计算,确实不难,但是效率会比较低。

一种类似动态规划的方法,按照下标i从小到大,依次计算 next[i],并且 next[i] 的计算通过前面已经计算出来的 next[0],next[1],……,next[i-1] 来推导。

KMP算法的时间复杂度是 \(O(n+m)\),不过它的分析过程稍微需要一点技巧,不那么直观,你只要看懂就好了,并不需要掌握,在我们平常的开发中,很少会有这么难分析的代码。


  1. http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf↩︎