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;

 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[]="substring searching algorithm search";

 char p2[]="search";

 cout BM(p1,p2);

 return 0;

【数组与链表算法】矩阵算法在程序中常见的简单应用 | C++ 数组与链表都是相当重要的结构化数据类型，也都是典型线性表的应用。线性表用于计算机中的数据存储结构，按照内存存储的方式基本上可以分为以下两种：静态数据结构和动态数据结构。数组类型就是一种典型的静态数据结构，动态数据结构又称为链表。在我前面的算法系列文章都细致的对二者的使用方法做过讲解。