BM算法很详尽的算法讲解 - CSDN文库

BM算法很详尽的算法讲解

需积分: 50 15 浏览量更新于2023-03-03 评论 1 收藏 301KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余5页未读，立即下载

评论0

Eric_Wei

粉丝: 55
资源: 13

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈