本文主要是介绍C++BM算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
BM算法是一种非常著名的字符串查找算法：
在字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法则往往比KMP算法快上3－5倍。
下面我们介绍一下BM算法：
1,BM算法是Boyer-Moore算法的简称，由Boyer 和Moore提出.
2，BM算法也是一种快速串匹配算法，BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比较顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化.
3,滑动距离函数:
为方便讨论，BM算法的关键是，对给定的模式T＝＂t0t1…tm＂定义一个从字符到正整数的映射：
dist ：ｃ－＞｛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）个字符而无需进行比较。
如这样一个例子：
从FINDINAHAYSTACKNEEDLEINA中查找NEEDLE的过程：
i j 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23
F I N D I N A H A Y S T A C K N E E D L E I N A
0 5 N E E D L E
5 5 N E E D L E
11 4 N E E D L E
15 0 N E E D L E
排版不是很好排，请大家见谅
第一步：i=5，j=5失败 dist（N）= 5 所以右移到5+5=10处
第二步：i=10，j=5失败 无dist(S) 所以右移到10+6 =16处
第三步：i=15，j=4失败 dist(N) = 5 所以右移到15+5 = 20处匹配成功
实例代码:
#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;elsei--;}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[]="substring searching algorithm search";char p2[]="search";cout<<BM(p1,p2);return 0;
}
这篇关于C++BM算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
