字符串匹配之 BM算法

缘起

字符串匹配算法中有三个单模式算法，暴力算法、KMP算法和BM算法。本文介绍BM（Boyer-Moore）算法，据说
BM比KMP快3~5倍，还有文本处理软件中的查找(CTRL+F)和替换(CTRL+H)命令用的就是BM算法。

分析

回顾【2】中KMP算法的核心思想——就是前缀匹配如果失败的话，我该怎么办的问题. 抓住这个问题，我们就引入了next跳转数组. 注意, KMP是前缀匹配算法, 也就是字符的匹配是从前开始进行的. 而BM算法是后缀匹配算法，也就是字符的匹配是从后到前的. 类比于KMP关心——“text和pattern从对齐位开始匹配到失配了，我该跳转到pattern的那个位置继续进行匹配.” BM算法关心的是

text和pattern的后缀匹配失败了的话，我该向右移动pattern到何处继续和text的当前位置进行匹配?

也就是下图

​ 图1

我们需要知道长度L=?, 即向右移动多少才能是潜在的、或者说可能的匹配成功的位置?

即BM和KMP相同点都是——text的指针绝不后退. 不同点是KMP是前缀匹配算法，而BM是后缀匹配算法.

注意哈，在失配的情况下，pattern是绝不会向左移动的，只会向右移动（图1），为什么呢？ 向左移动没有意义啊~ 因为就是一路右移动过来的啊~

和KMP的基调是一致的——寻找有潜力的下一个匹配位置. 什么叫做有潜力呢? 就是所谓的必要条件——如果你连这个都不满足，肯定不会是匹配成功的.

那么什么是必要条件呢? 现在图1中A和B这两段已经是完全匹配了（再说一遍，BM是后缀匹配算法），根据KMP的思路，我们是不是不能浪费这点信息?

如果图1的L是匹配位置的话，我们来看看能推导出什么? 显然就是P和A,进而和B匹配咯~

你看看，和KMP一样，我们又化归为了pattern自身的性质.

因此，我们针对pattern的每个位置——pattern[i] 都要计算它的suffix[i]的值，即

对0<=i<m, suffix[i]=max{ 0<=k<=i+1 | pattern[i-k+1,…,i] = pattern[m-k, …, m-1]} , 其中m是pattern的长度

则因为求取max的集合不空——至少k=0在里面, 所以 0<=suffix[i]<=i+1

下面讲述 BM 算法的两个规则

  1. 坏字符规则
  2. 好后缀规则

什么叫做坏字符？什么叫做好后缀? 一图胜千言

​ 图2

BM算法的思路是，如果当前text和pattern失配了，则pattern该如何移动？ 按照坏字符规则，可以移动一个距离，按照好后缀规则，可以移动一个距离，那么两个距离之间 取max，就是本次应该移动的距离.

下面分别讲述坏字符规则和好后缀规则应该移动的距离. 注意，下面讨论的距离都是以向右为正.

坏字符规则

分两种情况

  1. 坏字符（下图是c）没出现在模式串P中，这时可以把模式串P移动到坏字符的下一个字符，继续比较，如下图：

    ​ 图3

    即模式串移动的距离=i+1=m-(m-1-i), 其中m-1-i 是字符pattern[i]距离pattern右端的距离。m是pattern的长度.

  2. 坏字符出现在模式串中，这时可以把模式串从右算起第一个出现的坏字符和母串的坏字符对齐，当然，这样可能造成模式串倒退移动（但是下图没有倒退，但其实因为是好后缀和坏字符规则取大，所以其实倒退的情况并不会发生——因为好后缀不会倒退），如下图：

    ​ 图4

    则模式串移动的距离=bmbc[‘f’]-(m-1-i), 其中m-1-i是失配处(即pattern[i]!=text[j+i])离模式串最右端的距离. 而 bmbc[‘f’] 是pattern中从右算起第一个字符’f’（注意，本情形的前提是坏字符’f’在模式串中存在）距离pattern最右端的距离. 为什么是最右边的’f’? 因为这样就不会漏掉匹配（谨慎）.

    综上，坏字符导致pattern（或者说text的指针，因为又是重新开始比较后缀，其实就是一个动，另一个不动嘛~）向右移动的距离是 bmbc[text[j+i]]-(m-i-1), 其中bmbc[i]表示字符i(强转为字符型数据)距离pattern最右端的距离. 对于在pattern中不存在的字符i， bmbc[i] 规定为m(这样，坏字符情形1也被纳入进来了)

好后缀规则

还是回归图1, 其实必要条件就是Pattern上有一段P和后缀B完全相同. 所以我们可以换个姿势来看这个问题，就是

​ 图5

从上图，我们可以知道

1
bmgs[m-1-suffix[i]] = m-1-i

成立

其中 bmgs[i] 的含义是如果在pattern[i]失配的话（即text[j+i]!=pattern[i]）,则模式串应该向右移动的距离（或者说是text的指针向右移动的距离）

而suffix[i]的含义你在图5也可以看出来了——就是从它出发的能与后缀匹配的最大长度. 或者看下图

​ 图8

但是我们想谨慎的移动，所以如果有x=suffix[i]=suffix[j], 但是i<j, 则m-1-i>m-1-j, 所以

bmgs[m-1-x] = m-1-j, 用图说话，就是图5中pattern[m-1-suffix[i]] 失配的话，如果存在2段儿和后缀

pattern[m-suffix[i],…,m-1] 匹配的话，则选择最靠右的那一段儿X，移动模式串，使X与pattern[m-suffix[i],…,m-1]匹配在一起. 这样移动的距离最小，不会错失匹配.

注意，对于所有的pattern[m-1-suffix[i]] 失配而言，它一定要移动m-1-i的距离. 因为你不是要匹配么? 那必要条件就是pattern[m-1-suffix[i]]右边完全匹配的那一段儿必须要匹配. 所以你可以放心大胆的移动到最靠右的和pattern[m-suffix[i],…,m-1] 匹配的那一段儿.

但是不是每个失配的pattern[i]都和pattern[m-1-suffix[i]]那样那么幸运——都有pattern中间的一段儿（即图5中间的非后缀的”bcde”）等着它. 你可以想象一下，将图5中间的这段儿”bcde”向左滑动，直至”bcde”被pattern的左端”吞没”, 关于这一点，你可以看看下图

​ 图6

即如果不存在像上面那样一个完整后缀（图5中的”bcde”）的情形，但是存在一段前缀（图6中的”cde”）的情形，则只需要移动前缀(图6的”cde”)使之与后缀（图6的”bcde”）的一部分(“cde”)重合即可. 注意，此时失配的字符可以是模式串首位的c到g字符中的任意一个，不可能不需要移动图6那么多，否则的话，就存在后缀情形了.

如果更差一点，既不存在前缀情形（图6）又不存在后缀（图5）呢? 那么就应该毫不犹豫的移动整个pattern的长度m. 就像下图

​ 图7

这很容易明白，因为如果一旦移动<m就可以匹配的话，一定存在前缀情形（图6）或者后缀情形（图5）.

但是有个问题要搞清楚——对于一个既存在前缀情形又存在后缀情形的情形，如下图所示

​ 图9

如上图所示，在pattern[i]!=text[j+i] 失配（即细实线处），但是pattern[i]既是后缀情形——即pattern[i+1,..,m-1]和两根细虚线之间的段儿是匹配的. 则按照后缀情形，pattern需要右移动L2的距离. 但是如果pattern[i]也属于前缀情形——也就是如果pattern[0]到粗实线这一段前缀中包含pattern[i](pattern[0,…,粗实线]=pattern[粗虚线,…,m-1]), 则按照前缀规则，应该移动L1的距离. 为了谨慎起见，还是以L2为准.

还有一个问题：比如图9，pattern[i]隶属于多个前缀的话（即有多根粗实线），则 要选最长的前缀，因为最长的前缀导致的pattern的移动最短, 这样最谨慎.

综上，我们使用c++实现BM算法如下

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include "stdafx.h"
#include <iostream>
using namespace std;
#define LOCAL

const int SIZE  = 256, MAX_P = 20, MAX_T = 30; // 最多256个字符, 模式串最长20个字符,  文本串最长30个字符

int bc[SIZE]; // 坏字符数组, bc[i] 表示字符i距离pattern最右端的距离， 如果pattern中有多个字符i,选取最靠右的那个

int gs[MAX_P]; // 好后缀数组, gs[i]表示在好后缀规则下，如果pattern[i]失配的话，模式串向右移动的距离

int suffix[MAX_P]; // 后缀数组

char p[MAX_P]; // 模式串
int m; // 模式串长度

char text[MAX_T]; // 文本串
int n; // 文本串长度

void bmbc() // 坏字符规则
{
	for (int i = 0; i<SIZE; i++) bc[i] = m; // 伊始都是m
	for (int i = 0; i<m; i++) bc[(unsigned char) p[i]] = m-i-1; // 所以最后在pattern中不存在的字符的bc值就是m, 后缀匹配过程中遇到这种字符，则模式串直接移动bc值-(m-1-i)=m-(m-1-i)=i+1, 因为如果存在多个字符，则以最右边的为准, 所以i的顺序从0到m-1
}

void bmsuffix() // 处理pattern得到其相应的后缀数组
{
	suffix[m-1] = m; // pattern[m-1]的后缀数组长度自然就是m
	for (int i = 0; i< m-1; i++)
	{
		int j = 0;
		while(j<=i && p[i-j] == p[m-1-j])j++;
		suffix[i] = j;
	}
}

void bmgs() // 好后缀规则
{
	bmsuffix();
	for (int i = 0;i<m; i++) gs[i] = m; // 初始化都是默认既不是前缀规则又不是后缀情形的
	for (int i = m-2; ~i; i--) // i=m-1的时候, 下面的for不会进行的，所以干脆放掉
	{
		if (suffix[i] == i+1) // 如果是前缀情形, 则只需要处理最长前缀就可以了，所以i是从m-1往0跑的
		{
			for (int j = 0; j<m-i-1;j++) gs[j] = m-i-1;
			break; // 一旦发现，就只做一次
		}
	}
	for (int i=0; i<m-1; i++) gs[m-1-suffix[i]] = m-1-i; // 显然，i不能等于m-1, 否则suffix[m-1]=m, 难道gs[-1]啊?
}

void bm() // bm算法
{
	bmbc();
	bmgs(); // 预处理pattern
	int j = 0, i;
	while(j<=n-m)
	{
		i = m-1;
		while(~i && text[j+i]==p[i])i--; // 开始进行后缀匹配
		if (!~i)
		{
			printf("%d\n", j); // 发现一次匹配
			j+=gs[0]; // 注意，没有坏字符, 这里按照好后缀规则移动, 这里选择gs[0] 是因为假设pattern[0]失配了. 因为你要匹配的话，必要条件是pattern[1,...,m-1]也都匹配吧? 所以根据必要条件，这里选择gs[0]是可以的.
		}
		else // 失配
		{
			j+=max(gs[i], bc[text[j+i]]-(m-i-1)); //坏字符规则和好后缀规则移动距离取大
		}
	}
}

void init()
{
	scanf("%s%s", text, p);
	n = strlen(text);
	m = strlen(p);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	init();
	bm();
	return 0;
}
/*
测试数据
GoogleyouGooglelove
Google
*/

参考

【1】https://www.cnblogs.com/xubenben/p/3359364.html

【2】https://yfsyfs.github.io/2019/06/17/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95%E4%B9%8Bkmp/