1,BM算法是Boyer-Moore算法的简称,由Boyer 和Moore提出.
2,BM算法也是一种快速串匹配算法,BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比较顺序改为从右向左,但匹配发生失败时,模式T右移的计算方法却发生了较大的变化.
3,滑动距离函数:
为方便讨论,BM算法的关键是,对给定的模式T="t0t1…tm"定义一个从字符到正整数的映射:
dist :c->{1,2,…,m+1}
函数dist称为滑动距离函数,它给出了正文中可能出现的任意字符在模式中的位置。函数dist定义如下:
dist(c) = m-j j为c在模式中的下标,以后面的为准
dist(c) = m+1 若c不在模式中或c = tm
例如,T="pattern",则dist(p)= 6 – 0 = 6, dist(a)= 6 – 1 =5,
dist(t)= 6 – 3 =3,dist(e)= 2, dist(r)= 1, dist(n)= 6 + 1 = 7。
4,BM算法的基本思想是:假设将主串中自位置i起往左的一个子串与模式进行从右到左的匹配过程中,若发现不匹配,则下次应从主串的i + dist(si)位置开始重新进行新一轮的匹配,其效果相当于把模式和主串向右滑过一段距离dist(si),即跳过dist(si)个字符而无需进行比较。
一个具体的例子,如下图所示:
5,实例代码:
#include <iostream>
#include <cstring>
using namespace std;
int Dist(char *t,char ch)
{
int len = strlen(t);
int i = len - 1;
if(ch == t[i])
return len;
i--;
while(i >= 0)
{
if(ch == t[i])
return len - 1 - i;
else
i--;
}
return len;
}
int BM(char *s,char *t)
{
int n = strlen(s);
int m = strlen(t);
int i = m-1;
int j = m-1;
while(j>=0 && i<n)
{
if(s[i] == t[j])
{
i--;
j--;
}
else
{
i += Dist(t,s[i]);
j = m-1;
}
}
if(j < 0)
{
return i+1;
}
return -1;
}
int main()
{
char p1[]="abcdfedcbf";
char p2[]="cdfe";
cout<<BM(p1,p2);
return 0;
}
- 大小: 20.2 KB
分享到:
相关推荐
BM算法.md
算法设计--串匹配问题:BF算法、KMP算法、BM算法.rar
【安全课件】第17讲bm算法.pptx
现在密码学第14讲BM算法
VC++编程实现了二元域的BM算法。Berlekamp-Massey 算法是一个少有的高效算法。只需要输入密文中的2l个比特,就可以产生LFSR的最小多项式,从而生成整个序列。这里的l是系统的线性复杂度。
串匹配BM算法、KMP算法、BF算法.doc
研究BM串匹配算法,分析国内外各种改进算法,结合其优缺点,增加对模式串串末字符或坏字符的邻接字符在模式串中的首次出现位置、存在性、惟一性的判断。根据判断的结果对移动距离重新设置,增加模式串移动距离,减少...
BM和SAD双目匹配算法,较为简单,适合初学者
基于掩蔽效应的BM-FXLMS算法.docx
串匹配问题:BF算法、KMP算法、BM算法定义.pdf
matlab开发相关算法、系统代码、设计文档、使用说明,供参考 matlab开发相关算法、系统代码、设计文档、使用说明,供参考 matlab开发相关算法、系统代码、设计文档、使用说明,供参考 matlab开发相关算法、系统代码...
BM算法 c语言实现 详细注解 高手作品
经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的,在主串中存在大量子串与模式串前缀或者后缀相同时效率较低,并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法,有效地...
BM3D降噪算法,很好的一个外国人写的matlab版本
实现BF算法的改进算法:KMP算法和BM算法; 对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。 附件中 3.3.h BF算法代码 3.5.h KMP算法代码 3.12.h BM算法代码
BM算法很详尽的算法讲解 BM算法(全称Boyer-Moore Algorithm)是一种精确字符串匹配算法(只是一个启发式的字符串搜索算法)。 BM算法不同于KMP算法,采用从右向左比较的方法,同时引入了两种启发式Jump规则,即Bad...
目前性能最好的图像去噪算法,里面有用MATLAB的实现
BM算法 一个小小的程序 仅供大家参考使用
bm 算法的简单实现,代码比较清晰,建议参考