BM和上一篇的BMP一样都是字符串匹配算法，BM没有BMP那么难理解。

BM也是由Robert S. Boyer和J Strother Moore的名字命名的。

BM：由坏字符规则和好后缀规则组成

下面我们使用一个例子来了解BM是如何高效的完成字符串的比较过程。

主串: ABCABCDAB ABCDABCDABDE

模式串: ABCDABD

我们要在主串中查到模式串是否存在

坏字符规则

图1

从模式串尾部开始和主串逐个字符比较，通过比较发现图1圈起来的主串“C”和模式串“B”不相等，我们称主串的“C”字符为坏字符。此时坏字符和模式串中字符“B”对应的位置(按数组下标格式)为5，坏字符“C”在模式串中从左至右最大的位置（按数组下标格式）为2,那么需要后移的位数为5-2=3，如图2，此时主串的空格和模式串的D不相等，当时在模式串中又没有空格，当么坏字符在模式串中的位置为-1，所以模式串需要后移的位数为6 - （-1） = 7 如图3. 然后主串的字符C继续和模式字符D比较不相等，因为主串当前的坏字符C在模式串中的位置为2，而坏字符和模式串的比较位置为6，所以后移的位数为6-2，如图4，然后再次比较，发现模式串在主串中已经匹配。开始位置：主串开始比较位置-模式串的下标最大值

图2

图3

图4

后移位数=坏字符和模式的比较位置(数组下标) - 坏字符在模式串中的位置(匹配的最大下标)

说明：坏字符在模式中可能存在多个。我们只能在模式串中未匹配的字符中查找，不能到已经匹配的字符中查找，这样会造成后移位数为负的情况。

好后缀规则：

图5

如图5，尾部匹配的字符串我们称为“好后缀”， 其中D, CD, BCD 都是好后缀。

好后缀有下面几个以下几点规则需要记住：

1. 好后缀的位置都是从模式串的最后一个字符(按数组下标位置)计算的。如图5的好后缀的位置为6，
2. 如果好后缀在未匹配的模式串中不存在即在模式串只有一份，那么此时好后缀在模式串中的上一次匹配位置就为-1。
3. 如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。如图5，上一次的匹配位置为1，所以后移位数为4-1=3，移动后如图6

图6

从图6可以看到经过好后缀规则移动后，主串的A字符和模式串的D字符不相等，而此时没有好后缀的规则，所以需要坏字符规则，那么就需要后移6-0=6位，移动后如图7

图7

图7和图6一样，需要使用坏字符规则进行后移，后移6-2=4位，移动后如图8

图8

此时从图8可以看到，字串在主串中已经找到。

BM算法后移的规则：

1.如果有好后缀那么就通过好后缀规则算出后移位数，然后坏字符规则计算出的后移位数进行比较，取最大的那个后移位数。

2.如果没有好后缀那么直接坏字符规则进行后移

BM算法的实现C语言版本

为了提高提高匹配效率，BM在匹配过程中依赖bc，suffix，prefix3个数组

bc的大小为ascii码表的大小256。

suffix和prefix的大小为模式的大小。

#include <stdio.h>
#include <string.h>

//计算模式各字符的的ascii码对应的下标，如果出现相同字符取存最大下标
void GenerateBC(int *bc, char *p, int plen){
    int i;
    for(i = 0 ; i < 256; i++){
        bc[i] = -1;
    }
    for(i = 0 ; i < plen; i++){
        bc[(int)p[i]] = i;
    }
}
//计算好后缀
void GenerateGS(char *p, int *suffix, int* prefix, int plen){
    int i, j,k;
    for(i = 0 ; i < plen; i++){
        suffix[i] = -1;
        prefix[i] = -1;
    }
    i = 0;
    for(i = 0; i < plen - 1; i++){
        j = i;
        k = 0;// 公共后缀子串长度
        while(j >= 0 && p[j] == p[plen-k-1]){
            j--;//模式串前缀下标
            k++;
            suffix[k] = j + 1;//模式串上一次匹配的位置
        }
        if(j == -1){
            prefix[k] = 1; //在模式串中以首字符开始能找到和好后缀匹配的字串
        }
    }
}

int moveByGS(int pj, int plen, int *suffix, int* prefix){
    int i = 0;
    int k = plen - pj + 1; //坏字符对应的好后缀字符个数
    //坏字符对应的最大好后缀在模式串中能够找到
    if(suffix[k] != -1) return k - suffix[k] + 1; //坏字符在模式串的位置-坏字符在模式串上一次匹配的位置
    for(i = pj+2; i < plen; i++){//如果上一步，坏字符的好后缀，在模式串中只存在一次，那么需要遍历当前坏字符对应的所以好后缀，找到和前缀完全匹配的好后缀位置
        if(prefix[plen-i] != -1){
            return prefix[plen-i];
        }
    }
    return plen;//如果上面的条件都不满足那么需要后移整个模式
}

int BM(char *s, int slen, char *p, int plen,int *bc, int *suffix, int* prefix){
    int i=0 ,j;
	GenerateBC(bc, p, plen);
	GenerateGS(p, suffix, prefix, plen);
    while(i <= slen - plen){
        for(j = plen-1; j >= 0; j--){
            if(s[i+j] != p[j]){
				break;
			}
		}
        if(j < 0){
            return i;//匹配成功，返回主串与模式串第一个匹配的字符的位置
        }
		int bc_cnt = j - bc[(int)s[i+j]];//坏字符规则，当前坏字符位置-坏字符在模式中的最大值
		int gs_cnt = 0;
		if(j < plen-1){//如果模式串存在好后缀
			gs_cnt = moveByGS(j, plen, suffix, prefix);
		}
		int move_cnt = gs_cnt > bc_cnt ? gs_cnt : bc_cnt; //取坏字符和好后缀的最大后移位数
		i = i + move_cnt; //主串后移指定的位数，然后和模式串重新开始比较

    }
	return -1;
}

int main(){
    //char *s = "ABCABCDABABCDABCDBCDE";
    //char *p = "ABCDBCD";
    char *s = "ABCABCDAB ABCDABCDABDE";
    char *p = "ABCDABD";
    int bc[256] = {0x00};
    int suffix[strlen(p)];
    int prefix[strlen(p)];
    int start = BM(s, strlen(s), p, strlen(p), bc, suffix, prefix);
	printf("sart:%d\n", start);
	return 0;
}