BM算法笔记：

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     IN A      H     A      YS      T      A       C     KN E E     D      L     E I       N      A

0   5   N     E      E      D     LE

5   5                                           N     E      E      D     LE

11 4                                                                                           N       E       E     DL E

15 0N     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<stdlib.h>

#include<cstring>

using namespace std;

int dist(char *t,char ch) { //算出dist（）的值

int len = strlen(t);      //求子串的长度

int i = len - 1; //用于遍历子串内各字符的下标并从0开始计数

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 x = strlen(s);

int y = strlen(t);

int i = y - 1;

int j = y - 1;

while (j >= 0&&i<x) {

if (s[i] == t[j]) {

i--;

j--;

}

else {

i += dist(t,s[i]);//移动位置为坏字符在主串的位置+该字符在子串的值

j = y - 1; //子串回到最右边

}

}

if (j < 0) {

return i + 1;

}

return -1;

}

int main() {

char a[] = "ababcabcacbab";

char b[] = "abcac";

cout << BM(a, b) << endl;

system("pause");

return 0;

}