BM算法也是一种字符串快速匹配算法。相对于KMP算法,BM算法往往比KMP快3-5倍。二者的区别在与匹配操作的方向不同,BM算法是将字符串左对齐,然后从右向左匹配,当匹配失败时,模式T右移的计算方法却发生了较大的变化。
public class BM {
/**
* @param c 主串(源串)中的字符
* @param T 模式串(目标串)字符数组
* @return 滑动距离
*/
private static int dist(char c, char T[]) {
int n = T.length;
if (c == T[n - 1]) {
return n;// c出现在模式串最后一位时
}
for (int i = n; i >=1; i--) {
if (T[i - 1] == c)
return n - i;// i=max{i|t[i-1]且0<=i<=n-2}
}
return n;// c不出现在模式中时
}
/**
* @param p_s
* @param p_t
* @return -2错误,-1匹配不到,[0,p_s.length-p_t.length]表示t在s中位置,下标从0开始
*/
public static int index(final String p_s, final String p_t) {
if (p_s == null || p_t == null) {
return -2;
}
char[] s = p_s.toCharArray();
char[] t = p_t.toCharArray();
int slen = s.length, tlen = t.length;
if (slen < tlen) {
return -1;
}
int i = tlen, j;
while (i <= slen) {
j = tlen;
while (j > 0 && s[i - 1] == t[j - 1]) {// S[i-1]与T[j-1]若匹配,则进行下一组比较;反之离开循环。
i--;
j--;
}
if (0 == j){// j=0时,表示完美匹配,返回其开始匹配的位置
return i ;//如果要匹配多个,这里改为:int pos=i;i = i+tlen+1; --其中每次这个pos就是位置
}else{
//System.out.println(dist(s[i - 1], t));
i = i + dist(s[i - 1], t);// 把主串和模式串均向右滑动一段距离dist(s[i-1]).即跳过dist(s[i-1])个字符无需比较
}
}
return -1;// 模式串与主串无法匹配
}
public static void main(String[] args) {
String s = "faabc";
String t = "abc";
System.out.println("==========:"+index(s,t));
}
}
分享到:
相关推荐
BM算法 c语言实现 详细注解 高手作品
BM算法很详尽的算法讲解 BM算法(全称Boyer-Moore Algorithm)是一种精确字符串匹配算法(只是一个启发式的字符串搜索算法)。 BM算法不同于KMP算法,采用从右向左比较的方法,同时引入了两种启发式Jump规则,即Bad...
基础算法BM算法 密码学非常重要的算法!包括整个工程
实现BF算法的改进算法:KMP算法和BM算法; 对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。 附件中 3.3.h BF算法代码 3.5.h KMP算法代码 3.12.h BM算法代码
BM算法和sunday算法相关的原始论文
BM算法的相关资源吧,前两天看的,和大家分享
BM算法改进版,可从txt里读取序列,并连续计算。
基于BM算法的BCH码的译码器硬件实现,陈黎明,,BCH码是一种理论上比较成熟的代数码型,在电力通信系统,GSM标准的语音和数据业务,以及卫星通信和数字广播通信(DVB-S2)等多个领域
C++实现串匹配的BF,BM算法 C++实现串匹配的BF,BM算法 C++实现串匹配的BF,BM算法
BM算法原理图示详细讲解
这是一个文本字符查询程序,使用.net core编写,其中算法部分使用BM算法支持同步多文本查询。可以单字符查询和多字符查询。
BM算法的实现,GCC编译可用
AC-BM算法 多模式匹配代码
比KMP更快的字符串匹配算法——BM算法,排序算法数据结构 最快的排序算法
从网络入侵检测中提炼出的BM算法,已在VC6中调试通过.
根据信息安全课程中学习的密码学算法用程序编辑了BM算法-Matlab程序
BM算法,用于计算序列的线性复杂度及其反馈多项式。使用JAVA实现
BM算法是移位寄存器中的经典算法,可以快速由序列产生极小多项式
BM算法求线性综合解和DES加密是用C++写的,DSA签名使用java写的。
该算法主要用于计算机视觉,双目相机左右图像经过该算法可以得到视差图。