Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1610575
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2021-01-11 14:24:22

之前写过两篇关于kmp的文章,今天发现这货,据说当pattern串长度较大的时候,表现比kmp高3-4被,果断学起来啊~
首先,BM算法中的两个比较重要的概念就是坏字符和好后缀
1. 关于坏字符
BM匹配算法跟常识性的匹配算法不同的地方,首先就在于BM匹配算法,是从模式串的最后一位开始,向前开始匹配的。
当发现第一个不匹配的位置的时候,就会出现所谓的坏字符,比如
src:a b c d e f g
pat:h  i j k
其中坏字符就是'd',当找到坏字符的时候,我们要记录pattern串当前的下标p_i以及pattern串最大的坏字符的下标(没有按照-1处理)s_i,这样将pattern串向右滑动(p_i-s_i)个字符继续匹配即可。比如:
src: a b c d e f g
pat: b c d
第一个坏字符是'c',p_i 是2,坏字符'c'对应的s_i是1,所以pattern串向右滑动一个字符继续匹配即可

但是,如果只是有坏字符的话,是有可能使pattern串向左滑动的,比如:
src: a a a a a a a a a
pat: b a a a 
这时就需要第二个关键先生——好后缀登场了
2. 好后缀
首先,好后缀是指在匹配的过程中已经匹配的字符串叫做好后缀,如果好后缀在模式串前半部分有匹配的,那么就直接挪到两两匹配,规则可以参照坏字符;如果没有,就需要计算好后缀的后缀集合与模式串的前缀集合相同的最大交集,以此来决定后移多少,比如:
src: a c a b c b c b a c 
pat: a b b c a b c
这里pattern串直接后移到 第一个bc匹配即可
src: a c a b c b c b a c 
pat:         a b b c a b c
至于代码,坏字符本身不难,只需要记录pattern串每个字符出现的最大下标位置即可,这里说一下好后缀:
首先,好后缀的求解分为两个部分:
a). 好后缀good_suffix在pattern串中存在相同且在其前面的good_suffix,这里只需要记录每个后缀的前向最早出现即可;
这里需要引入一个suffix数组,suffix[i]表示长度为i的模式串后缀在其之前出现的下标,没有则置-1
b)好后缀good_suffix在pattern串中不存在相同且在其前面的good_suffix,就需要求好后缀的后缀和pattern串的前缀的最大匹配
这里需要引入另一个prefix数组,prefix[i]表示长度为i的模式串后缀,是否能够匹配模式串相应的前缀,这里贴上一波这两个数组的求法

点击(此处)折叠或打开

  1. void generate_good_suffix(string &pattern, int len, vector<int> &suffix, vector<bool> &prefix){
  2.     for(int i =0; i < len; i++){
  3.         suffix[i]=-1;
  4.         prefix[i]=false;
  5.     }
  6.     for(int i = 0; i<len-1;i++){
  7.         int j = i;
  8.         int k = 0;
  9.         while(j>=0 && pattern[j]==pattern[len-1-k]){
  10.             j--;
  11.             k++;
  12.             suffix[k]=j+1;
  13.         }
  14.         if(j==-1)prefix[k]=true;
  15.     }
  16. }




阅读(19043) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~