太原集团网站建设,网站建设有什么意义,佛山商城网站制作,用flash做的经典网站文章目录1. BM#xff08;Boyer-Moore#xff09;算法1.1 坏字符规则1.2 好后缀规则1.3 两种规则如何选择2. BM算法代码实现2.1 坏字符2.2 好后缀2.3 完整代码2.4 调试3. 总结1. BM#xff08;Boyer-Moore#xff09;算法
思想#xff1a;有模式串中不存在的字符#xf…
文章目录1. BMBoyer-Moore算法1.1 坏字符规则1.2 好后缀规则1.3 两种规则如何选择2. BM算法代码实现2.1 坏字符2.2 好后缀2.3 完整代码2.4 调试3. 总结1. BMBoyer-Moore算法
思想有模式串中不存在的字符那么肯定不匹配往后多移动几位提高效率 BM原理坏字符规则好后缀规则
1.1 坏字符规则 利用坏字符规则BM算法在最好情况下的时间复杂度非常低是On/m。比如主串是aaabaaabaaabaaab模式串是aaaa。每次比对模式串都可以直接后移四位所以匹配具有类似特点的模式串和主串的时候BM算法非常高效。单纯使用坏字符规则还是不够的。因为根据 si-xi计算出来的移动位数有可能是负数比如主串是aaaaaaaaaaaaaaaa模式串是baaa。不但不会向后滑动模式串还有可能倒退。所以BM算法还需要用到“好后缀规则”。
1.2 好后缀规则 从好后缀的后缀子串中找一个最长的且和模式串的前缀子串匹配的 {v}滑动至 {v} 对齐
1.3 两种规则如何选择
分别计算好后缀和坏字符规则往后滑动的位数取大的作为滑动位数还可以避免负数
2. BM算法代码实现
2.1 坏字符
找到坏字符在模式串中的位置(有重复的则是靠后的那个) 采用哈希而不是遍历。
#define SIZE 256 //字符集字符数
void generateBadChar(char *b, int m, int *badchar)//(模式串字符b模式串长度m模式串的哈希表)
{int i, ascii;for(i 0; i SIZE; i){badchar[i] -1;//哈希表初始化为-1}for(i 0; i m; i){ascii int(b[i]); //计算字符的ASCII值badchar[ascii] i;//重复字符被覆盖记录的是最后出现的该字符的位置}
}int str_bm(char *a, int n, char *b, int m)
//只考虑坏字符方法的程序框架
{int *badchar new int [SIZE];//记录模式串中每个字符最后出现的位置generateBadChar(b,m,hash); //构建坏字符哈希表int i 0, j;while(i n-m1){for(j m -1; j 0; --j) //模式串从后往前匹配{if(a[ij] ! b[j])break; //坏字符对应模式串中的下标是j}if(j 0) //匹配成功{return i; //返回主串与模式串第一个匹配的字符的位置}//这里等同于将模式串往后滑动 j-badchar[int(a[ij])] 位i i (j - badchar[int(a[ij])]);}return -1;
}2.2 好后缀
在模式串中查找跟好后缀匹配的另一个子串在好后缀的后缀子串中查找最长的、能跟模式串前缀子串匹配的后缀子串
不考虑效率的话上面两个操作都可以暴力查找 解决办法 预先对模式串进行处理。 实现过程 预处理模式串填充suffixprefix
void generateGS(char *b, int m, int *suffix, bool *prefix)
//预处理模式串填充suffixprefix
{int i, j, k;for(i 0; i m; i)//两个数组初始化{suffix[i] -1;prefix[i] false;}for(i 0; i m-1; i)//b[0,i]{j i;k 0;//公共后缀子串长度(模式串尾部取k个出来分别比较)while(j 0 b[j] b[m-1-k])//与b[0,m-1]求公共后缀子串{--j;k;suffix[k] j1;//相同后缀子串长度为k时该子串在b[0,i]中的起始下标// (如果有多个相同长度的子串被赋值覆盖存较大的)}if(j -1)//查找到模式串的头部了prefix[k] true;//如果公共后缀子串也是模式串的前缀子串}
}计算滑动位数
case1 case2 case3以上都不成立移动整个模式串长度m
2.3 完整代码
/*** description: 字符匹配BM算法* author: michael ming* date: 2019/6/18 22:19* modified by: */
#include algorithm
#include string
#include iostreamusing namespace std;
#define SIZE 256 //字符集字符数
void generateBadChar(char *b, int m, int *badchar)//(模式串字符b模式串长度m模式串的哈希表)
{int i, ascii;for(i 0; i SIZE; i){badchar[i] -1;//哈希表初始化为-1}for(i 0; i m; i){ascii int(b[i]); //计算字符的ASCII值badchar[ascii] i;//重复字符被覆盖记录的是最后出现的该字符的位置}
}
void generateGS(char *b, int m, int *suffix, bool *prefix)//预处理模式串填充suffixprefix
{int i, j, k;for(i 0; i m; i)//两个数组初始化{suffix[i] -1;prefix[i] false;}for(i 0; i m-1; i)//b[0,i]{j i;k 0;//公共后缀子串长度(模式串尾部取k个出来分别比较)while(j 0 b[j] b[m-1-k])//与b[0,m-1]求公共后缀子串{--j;k;suffix[k] j1;//相同后缀子串长度为k时该子串在b[0,i]中的起始下标// (如果有多个相同长度的子串被赋值覆盖存较大的)}if(j -1)//查找到模式串的头部了prefix[k] true;//如果公共后缀子串也是模式串的前缀子串}
}
int moveByGS(int j, int m, int *suffix, bool *prefix)//传入的j是坏字符对应的模式串中的字符下标
{int k m - 1 - j;//好后缀长度if(suffix[k] ! -1)//case1找到跟好后缀一样的模式子串多个的话存的靠后的那个子串起始下标return j - suffix[k] 1;for(int r j 2; r m; r)//case2{if(prefix[m-r] true)//m-r是好后缀的子串的长度如果这个好后缀的子串是模式串的前缀子串return r;//在上面没有找到相同的好后缀下移动r位对齐前缀到好后缀}return m;//case3,都没有匹配的移动m位模式串长度
}
int str_bm(char *a, int n, char *b, int m)//a表示主串长n; b表示模式串,长m
{int *badchar new int [SIZE];//记录模式串中每个字符最后出现的位置generateBadChar(b,m,badchar); //构建坏字符哈希表int *suffix new int [m];bool *prefix new bool [m];generateGS(b, m, suffix, prefix); //预处理模式串填充suffixprefixint i 0, j, moveLen1, moveLen2;//j表示主串与模式串匹配的第一个字符while(i n-m1){for(j m -1; j 0; --j) //模式串从后往前匹配{if(a[ij] ! b[j])break; //坏字符对应模式串中的下标是j}if(j 0) //匹配成功{delete [] badchar;delete [] suffix;delete [] prefix;return i; //返回主串与模式串第一个匹配的字符的位置}//这里等同于将模式串往后滑动 j-badchar[int(a[ij])] 位moveLen1 j - badchar[int(a[ij])];//按照坏字符规则移动距离moveLen2 0;if(j m-1)//如果有好后缀的话{moveLen2 moveByGS(j,m,suffix,prefix);//按照好后缀规则移动距离}i i max(moveLen1,moveLen2);//取大的移动}delete [] badchar;delete [] suffix;delete [] prefix;return -1;
}int main()
{string a abcacabcbcbacabc, b cbacabc;cout a 中第一次出现 b 的位置(从0开始)是 str_bm(a[0],a.size(),b[0],b.size());return 0;
}2.4 调试
为方便调试将字符集SIZE改为3ascii int(b[i]-a)
坏字符在模式串中的位置靠后的那个 badchar[0]a是4 badchar[1]b是5 badchar[2]c是6预处理模式串 按规则移动
3. 总结
BM算法的内存消耗 整个算法用到了额外的3个数组其中bc数组的大小跟字符集大小有关suffix数组和prefix数组的大小跟模式串长度m有关。 如果处理字符集很大的字符串匹配问题badchar数组对内存的消耗就会比较多。 因为好后缀和坏字符规则是独立的如果运行的环境对内存要求苛刻可以只使用好后缀规则不使用坏字符规则就可以避免badchar数组过多的内存消耗。不过单纯使用好后缀规则的BM算法效率就会下降一些了。时间复杂度 以上BM算法是个初级版本。这个版本在极端情况下预处理计算suffix数组、prefix数组的性能会比较差。 比如模式串是aaaaaaa这种包含很多重复的字符的模式串预处理的时间复杂度就是Om^2。如何优化这种极端情况下的时间复杂度退化以后再找空研究。 实际上BM算法的时间复杂度分析起来是非常复杂论文A new proof of the linearity of the Boyer-Moore string searching algorithm证明了在最坏情况下BM算法的比较次数上限是5n。论文Tight bounds on the complexity of the Boyer- Moore string matching algorithm证明了在最坏情况下BM算法的比较次数上限是3n。 BM算法核心思想是利用模式串本身的特点在模式串中某个字符与主串不能匹配的时候将模式串往后多滑动几位以此来减少不必要的字符比较提高匹配的效率。BM算法构建的规则有两类坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存为了节省内存我们可以只用好后缀规则来实现BM算法。
