2025年BM算法详解

大家好，我是讯享网，很高兴认识大家。

1.http://blog.csdn.net/joylnwang/article/details/

2.http://www.cnblogs.com/dsky/archive/2012/05/04/2483190.html

一. 1977年，Robert S.Boyer和J Strother Moore提出了另一种在O(n)时间复杂度内，完成字符串匹配的算法，其在绝大多数场合的性能表现，比KMP算法还要出色，下面我们就来详细了解一下这一出色的单模式匹配算法，在此之前推荐读者读一下我的另一篇文章《KMP算法详解》，对于透彻理解BM算法大有裨益。

在讲解Boyer-Moore算法之前，我们还是要提一提KMP算法的老例子，当模式串与目标串匹配至如下位置时：

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
b	a	b	c	b	a	b	c	a	b	c	a	a	b	c	a	b	c	a	b	c	a	c	a	b	c
					a	b	c	a	b	c	a	c	a	b

我们发现target[13]!=pattern[7]，此时根据KMP算法的next值，我们将target[13]与pattern[5]对齐，再依次执行匹配。这里target[13]='a'。如果target[13]='d'，因为'd'不是模式串pattern中的字符，所以无论将target[13]与pattern中任何一个字符对齐都会匹配失败，所以当我们在匹配过程中发现target[i]是不属于模式串的字符，则我们可以直接将target[i+1]，与pattern[1]对齐，再向后执行匹配。这样就获得了更大的跳转幅度，同时也能保证匹配的正确性。这便是BM算法相较于KMP算法的一个重要改进。

BM算法之所以能够在单模式匹配中有更加出色的表现，主要是其使用了两个跳转表，一个是坏字符表（论文中称为delta1），一个是好后缀表（论文中称为delta2），下面我们以BM算法对目标串的一次匹配操作，来讲解这两个表的具体跳转策略，这里模式串为"AT-THAT"，目标串为"WHICH-FINALLY-HALTS.--AT-THAT-POINT"。

讯享网

	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
	W	H	I	C	H	-	F	I	N	A	L	L	Y	-	H	A	L	T	S	.	-	-	A	T	-	T	H	A	T	-	P	O	I	N	T
1	A	T	-	T	H	A	T
2								A	T	-	T	H	A	T
3												A	T	-	T	H	A	T
4																		A	T	-	T	H	A	T
5																							A	T	-	T	H	A	T

BM算法与KMP算法的最大的不同之处在于，当目标串与模式串在某个位置对齐之后，KMP算法是从对齐位置向后依次执行匹配（不一定是模式串的第一个元素）。而BM算法是从模式串的末尾位置（一定是模式串的最后一个元素）向前与目标串依次执行匹配。上面的例子，在4次模式串移动之后，就发现了匹配模式。

第一次，pattern[1]与target[1]对齐，从pattern[7]向前依次与target执行比较，但是第1次比较就发现，target[7]='F'，而'F'不是pattern串中的字符，所以target中包含target[7]的任何子串都不可能与pattern匹配，此时我们可以直接将pattern串滑动到target[7]之后，让pattern[1]与target[8]对齐，然后再由target[14]依次向前执行比较。

第二次，target[14]='-'，虽然'-'是模式串中的字符，但是如果要target串中包含target[14]的字串与pattern串匹配，则至少target[14]需与pattern中最后一个'-'对齐。而pattern中只有一个'-'pattern[3]，所以将target[14]，与pattern[3]对齐，然后再由target[18]向前依次执行比较。

第三次，虽然target[18]=pattern[7]='T'，但是target[17]='L'，'L'不是pattern中的字符，所以包含target[17]的任何字串都不可能与pattern匹配，所以pattern[1]直接与target[18]对齐再执行匹配。

第四次，target[23...24]=pattern[6...7]，target[22]!=pattern[5]，我们注意到，pattern[6...7]=pattern[1...2]所以pattern[1...2]也是模式串的一个自包含后缀（下文详述），所以我们可以令pattern[1]与target[23]对齐再向后执行匹配，此时我们就发现了满足条件的匹配串target[23...29]。

该示例使用到了BM算法中的所有跳转优化，大幅加速了模式串的向后滑动过程，实现了模式的快速匹配，其中第1，2，3次滑动使用的是算法中的坏字符移动规则，第4次滑动使用的是好后缀移动规则，那么什么是所谓的坏字符和好后缀规则呢。

所谓的坏字符移动规则，就是一个表，其以输入字符集的所有字符作为索引，每个输入字符c对应着一个值，表示如果目标串的当前位置字符c与模式串匹配失败，那么目标串当前位置应该可以向前滑动的步数。假设字符集为"ABCDEFGHIJKLMNOPQRSTUVWXYZ-"，那么他对应模式串"AT-THAT"的坏字符表为。

	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	-
delta1	1	7	7	7	7	7	7	2	7	7	7	7	7	7	7	7	7	7	7	0	7	7	7	7	7	7	4

坏字符表的定义为，对于输入字符集合中的字符c，如果c不在模式串中，则delta1[c]= patlen（模式串的长度），如果c在模式串中，则delta1[c]=j-i，其中，j是模式串最末元素的索引值，i是字符c在模式串中最右出现的位置（这里与Boyer-Morre两人的论文略有差别，主要是因为BM的论文中，字符串的索引从1开始，其最末元素的索引值，就等于模式串的长度，而在实际计算模式串中含有字符的坏字符滑动值时，使用到的是模式串最末元素的索引值，这个值与模式串的长度不一定相等）。下面就是用于生成坏字符表的代码，为了简单起见，这里没有使用字典结构，而是假设输入的字符只能是A-Z，然后将这26个字符映射到一个数组中。

[cpp] view plain copy

相关推荐