1977年，Robert S.Boyer和J Strother Moore提出了另一种在O(n)时间复杂度内，完成字符串匹配的算法，其在绝大多数场合的性能表现，比KMP算法还要出色，下面我们就来详细了解一下这一出色的单模式匹配算法，在此之前推荐读者读一下我的另一篇文章《字符串的模式匹配：KMP算法》，对于透彻理解BM算法大有裨益。
BM算法之所以能够在单模式匹配中有更加出色的表现，主要是其使用了两个跳转表，一个是坏字符表，一个是好后缀表。KMP是利用已经匹配部分的信息来移动；BM算法是做反向比较，并根据已经匹配的部分来确定移动量。
Boyer-Moore算法不仅效率高，而且构思巧妙，容易理解。但是，它并不是效率最高的算法，实际采用并不多。各种文本编辑器的”查找”功能（Ctrl+F），大多采用Boyer-Moore算法。
为了更好的理解BM算法，我们先看一下”简单的后比对算法”，然后介绍什么事”坏字符规则”和”好字符规则”， 再看一下这个”BM算法匹配过程”和”BM算法的具体实现”
时间复杂度：最差情况O（MN），最好情况O（N）
简单的后比对算法
假设有如下的字符串T和模式串P：
字符串T：”abacababc”
模式串P：”abab”
那么简单的后比对算法流程如下：
1、模式串的长度4，首先比较模式串P最后一个字符和字符串T同一个位置的字符
abacababc
abab
2、也就是比较T[3]和P[3], 字符"c"和"b"不匹配。然后整个模式串移1位。
abacababc
abab
3、比较T[4]和P[3], 即字符"a"和"b"不匹配。然后整个模式串移1位。
abacababc
abab
4、比较T[5]和P[3], 即字符"b"和"b"匹配。
然后比较T[4]和P[2]， 即字符"a"和"a"匹配。
再比较T[3]和P[1]，即字符"c"和"b"不匹配。
整个模式串移1位。
abacababc
abab
5、比较T[6]和P[3], 即字符"a"和"b"匹配。整个模式串移1位。
abacababc
abab
6、比较T[7]和P[3], 即字符"b"和"b"匹配。
字符串T和模式串P都往前移动1位，然后比较T[6]和P[2]， 即字符"a"和"a"匹配。
字符串T和模式串P都往前移动1位，然后比较T[5]和P[1]， 即字符"b"和"b"匹配。
字符串T和模式串P都往前移动1位，然后比较T[4]和P[0]， 即字符"a"和"a"匹配。
发现此处，字符串T和模式串P完全匹配，实现代码:
/*! int search_reverse(char const*, int, char const*, int)
*/bref 查找出模式串patn在主串src中第一次出现的位置
*/return patn在src中出现的位置，当src中并没有patn时，返回-1
*/
int search_reverse(char const* src, int slen, char const* patn, int plen)
{
int s_idx = plen, p_idx;
if (plen == 0)
return -1;
while (s_idx <= slen)//计算字符串是否匹配到了尽头
{
p_idx = plen;
while (src[--s_idx] == patn[--p_idx])//开始匹配
{
//if (s_idx < 0)
//return -1;
if (p_idx == 0)
{
return s_idx;
}
}
s_idx += (plen - p_idx)+1;
}
return -1
} 坏字符规则
那么提个疑问，在”简单的后比对算法”中，有没有发放可以尽可能跳过更多字符呢？
在上面的例子里面，第一步的时候，S[3] = ‘c’ != P[3]，下一步应该当整个模式串移过S[3]即可，因为S[3]已经不可能与P中的任何一个部分相匹配了。
那么对模式串于P中不存在的字符，我们可以直接跳过模式串P的长度，然后再进行比对。
如果P中存在的字符该怎么定位呢？我们举个例子，字符串T还是”abacababc”, 模式串P为”ced”。
那么根据尽可能跳过更多的字符和后比对原则，我们得到如下的匹配过程：
1、对齐字符串T和模式串P, 如下
abacababc
ced
2、比对T[2]和P[2], 即字符"a"和"d"不匹配。如果跳过尽可能多的字符呢，我们知道模式串P中有字符"c", 字符串T中位于模式串后1位的字符也是"c"。将字符串T和模式串P的字符"c"对齐。
abacababc
ced 由此总结，我们可以将T[2]与P[2]不匹配的字符，也就是字符”a”，称之为”坏字符”。而模式串移动位置 = 模式串长度 - 坏字符在模式串中上一次出现的位置 = 3 - 0 =3， 称之为坏字符规则。
如果坏字符没有出现在模式串中，那么坏字符在模式串中上一次出现的位置为-1
坏字符构建和坏字符规则匹配的具体实现：
/* 函数：void buildBadC(char *, int, int*)
* 目的：根据好后缀规则做预处理，建立一张好后缀表
* 参数：
* pattern => 模式串P
* plen => 模式串P长度
* shift => 存放坏字符规则表,长度为的int数组
*/
void buildBadC(char const* pattern, int plen, int* shift){
for( int i = 0; i < 256; i++ )
*(shift+i) = plen;
while ( plen >0 ){
*(shift+(unsigned char)*pattern++) = --plen;
}
}
/* int matchBadC(char const*, int, char const*, int)
* bref 查找出模式串patn在主串src中第一次出现的位置
* return patn在src中出现的位置，当src中并没有patn时，返回-1
*/
int matchBadC(char const* src, int slen, char const* patn, int plen, int* shift){
int s_idx = plen, p_idx;
int skip_stride;
if (plen == 0)
return -1;
// 计算字符串是否匹配到了尽头
while (s_idx <= slen) {
p_idx = plen;
// 开始匹配
while (src[--s_idx] == patn[--p_idx]){
//if (s_idx < 0)
//return -1;
if (p_idx == 0){
return s_idx;
}
}
skip_stride = shift[(unsigned char)src[s_idx]];
s_idx += (skip_stride>plen-p_idx ? skip_stride: plen-p_idx)+1;
}
return -1;
} 好后缀规则
在”简单的后比对算法”中算法流程的第3步执行后，情情况如下:
abacababc
abab 我们可以看到T[5]和P[3], 即字符”b”和”b”匹配。T[4]和P[2]， 即字符”a”和”a”匹配。
我们把这种情况称之为好后缀。在”简单的后比对算法”中，我们能总结出”ab”, “b”都是好后缀。
那么如何根据好后缀跳过尽可能多的字符呢？我们先将字符串T和模式串P字符对齐如下：
abacababc
abab 此时，我们可以总结出好后缀模式串P移动的位数=模式串长度 - 好后缀最后一个字符在模式串中上次出现的位置（也就是”b”在模式串P的位置） = 4 - 2 = 2位。
总结一句话，利用字符串T与模式串P已匹配成功的部分来找一个合适的位置方便下一次最有效的匹配。只是这里是需要寻找一个位置，让已匹配过的后缀与模式串中从后往前最近的一个相同的子串对齐。这也就是BM算法的精髓所在，理解这句话就等于理解了整个BM算法。
好后缀构建和好后缀规则匹配的具体实现：
/*
* 函数：void buildGoodC(char *, int, int*)
* 目的：根据最好后缀规则做预处理，建立一张好后缀表
* 参数：
* pattern => 模式串P
* plen => 模式串P长度
* shift => 存放最好后缀表数组
* 返回：void
*/
void buildGoodC(char const* pattern, int plen, int* shift){
shift[plen-1] = 1; // 右移动一位
char end_val = pattern[plen-1];
char const* p_prev, const* p_next, const* p_temp;
char const* p_now = pattern + plen - 2; // 当前配匹不相符字符,求其对应的shift
bool isgoodsuffixfind = false; // 指示是否找到了最好后缀子串,修正shift值
for( int i = plen -2; i >=0; --i, --p_now){
p_temp = pattern + plen -1;
isgoodsuffixfind = false;
while ( true ){
while (p_temp >= pattern && *p_temp-- != end_val); // 从p_temp从右往左寻找和end_val相同的字符子串
p_prev = p_temp; // 指向与end_val相同的字符的前一个
p_next = pattern + plen -2; // 指向end_val的前一个
// 开始向前匹配有以下三种情况
//第一：p_prev已经指向pattern的前方,即没有找到可以满足条件的最好后缀子串
//第二：向前匹配最好后缀子串的时候,p_next开始的子串先到达目的地p_now,
//需要判断p_next与p_prev是否相等,如果相等,则继续住前找最好后缀子串
//第三：向前匹配最好后缀子串的时候,p_prev开始的子串先到达端点pattern, 这个可以算是最好的子串
if( p_prev < pattern && *(p_temp+1) != end_val ) // 没有找到与end_val相同字符
break;
bool match_flag = true; //连续匹配失败标志
while( p_prev >= pattern && p_next > p_now ) {
if( *p_prev --!= *p_next-- ){
match_flag = false; //匹配失败
break;
}
}
if( !match_flag )
continue; //继续向前寻找最好后缀子串
else {
//匹配没有问题, 是边界问题
if( p_prev < pattern || *p_prev != *p_next) {
// 找到最好后缀子串
isgoodsuffixfind = true;
break;
}
// *p_prev == * p_next 则继续向前找
}
}
shift[i] = plen - i + p_next - p_prev;
if( isgoodsuffixfind )
shift[i]--; // 如果找到最好后缀码，则对齐，需减修正
}
}
/* int matchGoogC(char const*, int, char const*, int)
* bref 查找出模式串patn在主串src中第一次出现的位置
* return patn在src中出现的位置，当src中并没有patn时，返回-1
*/
int matchGoogC(char const* src, int slen, char const* patn, int plen, int* shift) {
int s_idx = plen, p_idx;
int skip_stride;
if (plen == 0)
return -1;
// 计算字符串是否匹配到了尽头
while (s_idx <= slen){
p_idx = plen;
// 开始匹配
while (src[--s_idx] == patn[--p_idx]){
//if (s_idx < 0)
//return -1;
if (p_idx == 0){
return s_idx;
}
}
skip_stride = shift[p_idx];
s_idx += skip_stride +1;
}
return -1;
} BM算法匹配过程：
字符串： here is a simple example
搜索词： example
1、首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。也就是比较字符串的's'和搜索词的'e'。
here is a simple example
example
2、这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符（整体上）肯定不是要找的结果。
我们看到，"s"与"e"不匹配。这时，"s"就被称为"坏字符"（bad character），即不匹配的字符。
我们还发现，"s"不包含在搜索词"example"之中，这意味着可以把搜索词直接移到"s"的后一位。
here is a simple example
example
3、依然从尾部开始比较，发现"p"与"e"不匹配，所以"p"是"坏字符"。但是，"p"包含在搜索词"example"之中。
所以，将搜索词后移两位，两个"p"对齐。
here is a simple example
example
由此总结出"坏字符规则"：
搜索词后移位数 = 坏字符本次在搜索词中不匹配的位置 - 搜索词中的上一位出现位置。
如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。
以"p"为例，它作为"坏字符"， 坏字符本次在搜索词中不匹配的位置， 也就是搜索词最后一个字符"e"的位置。
最后一个字符"e"在搜索词中是第6位（从0开始编号）。
而"p"在搜索词中的上一次出现位置为4，所以整个搜索词后移 6 - 4 = 2位。
再以前面第1步的"s"为例，它出现在第6位，上一次出现位置是 -1（即未出现），则整个搜索词后移 6 - (-1) = 7位。
4、搜索词后移两位后，两个"p"对齐。
here is a simple example
example
依然从尾部开始比较，simple中的"e"与搜索词中的"e"匹配。再比较前面一位，simple中的"le"与搜索词中的"le"匹配。
此时存在字符串中的"mple"、"ple"、"le"、"e"与搜索词中的"mple"、"ple"、"le"、"e"匹配.
我们把这种情况称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，"mple"、"ple"、"le"、"e"都是好后缀。
5、依此从后往前匹配，直到simple中的"i"与搜索词中的"a"不匹配。根据"坏字符规则"，此时搜索词应该后移 2 - （-1）= 3 位。
here is a simple example
example
6、那么此时有没有更好的移法？我们知道，此时存在"好后缀"。所以，可以采用"好后缀规则"：
搜索词后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置。
这个规则有三个注意点：
（1）"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。
（2）如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。
比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。
（3）如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。
比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？
回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。
这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。
此时，所有的"好后缀"（MPLE、PLE、LE、E）之中，只有"E"在"EXAMPLE"还出现在头部，所以后移 6 - 0 = 6位。
here is a simple example
example
7、可以看到，"坏字符规则"只能移3位，"好后缀规则"可以移6位。所以，BM算法的基本思想是，每次后移这两个规则之中的较大值。
更巧妙的是，这两个规则的移动位数，只与搜索词有关，与原字符串无关。
因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。具体实现：
/*
* 函数：int* BMSearch(char *, int , char *, int, int *, int *)
* 目的：判断文本串T中是否包含模式串P
* 参数：
* src => 文本串T
* slen => 文本串T长度
* ptrn => 模式串P
* pLen => 模式串P长度
* bad_shift => 坏字符表
* good_shift => 最好后缀表
* 返回： int - 1表示匹配失败，否则反回
*/
int BMSearch(char const*src, int slen, char const*ptrn, int plen, int const*bad_shift, int const*good_shift) {
int s_idx = plen;
if (plen == 0)
return 1;
//计算字符串是否匹配到了尽头
while (s_idx <= slen){
int p_idx = plen, bad_stride, good_stride;
//开始匹配
while (src[--s_idx] == ptrn[--p_idx]){
//if (s_idx < 0)
//return -1;
if (p_idx == 0){
return s_idx;
}
}
// 根据坏字符规则计算跳跃的距离
bad_stride = bad_shift[(unsigned char)src[s_idx]];
// 根据好后缀规则计算跳跃的距离
good_stride = good_shift[p_idx];
// 当匹配失败的时候，取坏字符规则和好后缀规则大者向前滑动
s_idx += ((good_stride > bad_stride) ? good_stride : bad_stride )+1;
}
return -1;
} 参考博文：
http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
http://blog.csdn.net/v_JULY_v/article/details/6545192