加载中…
个人资料
枝叶飞扬
枝叶飞扬
  • 博客等级:
  • 博客积分:0
  • 博客访问:1,914,072
  • 关注人气:217
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Boyer-Moore算法详解一

(2013-10-27 09:56:40)
标签:

bm算法

后缀匹配

it

分类: 数学

转自:http://www.searchtb.com/2011/07/字符串匹配那些事(一).html


后缀匹配,是指模式串的比较从右到左,模式串的移动也是从左到右的匹配过程,经典的BM算法其实是对后缀蛮力匹配算法的改进。所以还是先从最简单的后缀蛮力匹配算法开始。下面直接给出伪代码,注意这一行代码:j++;BM算法所做的唯一的事情就是改进了这行代码,即模式串不是每次移动一步,而是根据已经匹配的后缀信息,从而移动更多的距离。

1
2
3
4
5
6
7
8
j = 0;
while (j <= strlen(T) - strlen(P)) {
   for (i = strlen(P) - 1; i >= 0 && P[i] ==T[i + j]; --i)
   if (i < 0)
      match;
   else
      ++j;
}

为了实现更快移动模式串,BM算法定义了两个规则,好后缀规则和坏字符规则,如下图可以清晰的看出他们的含义。利用好后缀和坏字符可以大大加快模式串的移动距离,不是简单的++j,而是j+=max (shift(好后缀), shift(坏字符))

先来看如何根据坏字符来移动模式串,shift(坏字符)分为两种情况:

  • 坏字符没出现在模式串中,这时可以把模式串移动到坏字符的下一个字符,继续比较,如下图:

  • 坏字符出现在模式串中,这时可以把模式串第一个出现的坏字符和母串的坏字符对齐,当然,这样可能造成模式串倒退移动,如下图:


为了用代码来描述上述的两种情况,设计一个数组bmBc['k'],表示坏字符‘k’在模式串中出现的位置距离模式串末尾的最大长度,那么当遇到坏字符的时候,模式串可以移动距离为: shift(坏字符) = bmBc[T[i]]-(m-1-i)。如下图:

数组bmBc的创建非常简单,直接贴出代码如下:

1
2
3
4
5
6
7
void preBmBc(char *x, int m, int bmBc[]) {
    int i;
    for (i = 0; i < ASIZE; ++i)
         bmBc[i] = m;
    for (i = 0; i < m - 1; ++i)
         bmBc[x[i]] = m - i - 1;
}


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有