BM 算法详细图解 编著：WeiSteve@Yeah.net [Weisteven]
2010/10/29 于 HoHai University 4216
BM 算法详细图解
BM 算法（全称 Boyer-Moore Algorithm）是一种精确字符串匹配算法（只是一个
启发式的字符串搜索算法）。
BM 算法不同于 KMP 算法，采用从右向左比较的方法，同时引入了两种启发式 Jump
规则，即 Bad-Character 和 Good-Suffix，来决定模板向右移动的步长。
BM 算法的基本流程:
文本串 T（待匹配的字符串，长度 n），模式串为 P（用于去匹配的字符串模板，
长度设为 m）。
首先将 T 与 P 进行左对齐，然后进行从右向左比较（此时不移动模板和文本的相
对位置，仅仅比较对齐位置上面是否相同，方向是右向左），如下图所示:
若是某趟比较不匹配时，BM 算法就采用两条启发式规则，即前面提到的
Bad-Character 和 Good-Suffix，来计算模式串 P 向右移动的步长（取两种方式求
得的移动步长的较大的），直到整个匹配过程的结束。
下面，来详细介绍一下 Bad-Character 和 Good-Suffix：
请看下图：
T
P
A
B
C
E
C
A
B
E
A
B
C
A
B
评论0