今天继续昨天的话题，字符串匹配算法之 BM 算法，BM 可以说是继 KMP 算法之后更加优秀的字符串匹配算了，BM 是大师 Boyer-Moore 的算法杰作， 所以称 BM 算法，相比 KMP 算法效率提高了不少，在空间上 BM 算法需要一个跟匹配字符集相同的辅助空间，已存放不同的匹配字符，比 KMP 要浪费不少，但是这也是 BM 的特色，可以在不同的字符集使用，两个字符集的话那就放一个字符集同大小的辅助空间就好，最复杂字符就很好了，目前大部分的高级语言比如 C# 都使用了 BM 及其改进算法 (AC-BM 算法)，相比 KMP 匹配两个中文字符出现的半角结果而言，我还是偏好 BM ，虽然浪费空间，但是，实现接近低于线性的消耗，少了一个 n 以上的的匹配时间，这点也是客观的
BM 算法还有很多衍生算法 AC-BM 算法就是一种，用数学方法进行了优化，最好情况提高了一个常数级，提高了索引利用效率，这个下次有空再写吧 算法原理：从字符串后扫描，利用了匹配后缀和无效字符的替换原则，总体效率提高不少 算法如下，具体的算法注释已经添加不懂的话，请留言或者跟我联系，我有时间会尽量解答
调试欢迎，TC 环境，GCC 下没时间调试，改改应该没有问题 BM 字符串匹配算法：
/*BM 字符串匹配算法 */
/*code by CG lidaren.com
* ACM yctc
*2008 12 20
*/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define LEN 256
/*LEN 使用一个 character set ASCII 编码使用一个字节表示字符，UNICODE 要另
* 外考虑，BM 算法优势所在 */
/*BM () BM 算法基本功能函数
* 输入:
* char *s 匹配串
* char *p 模式串
* int index 匹配开始索引
* int post [] 辅助数组
* 返回:
* int 下一个匹配开始的索引，匹配失败返回 - 1
*/
int BM(char *s, char *p, int index, int post[]) {
int len = strlen(s);
int i,j, next;
i = strlen (p)-1;/* 字符串长度减 1*/
j = index+strlen (p)-1;/* 第一次调用 BM () 时 index = 0，因
* 为下面的 for 循环是从模式串的末尾开始比较，所以匹配串的初始比较位
* 置应该是从开头数模式串长度个位置开始。*/
*/
for(; i>=0; i--, j--) {
if (s [j] != p [i]){/* 第一个字符的匹配 */
break;
}
}/*for*/
if (i<0) /* 匹配完毕？*/
return 0; /* 匹配成功 */
else if(post[s[j]]>0)
/* 当出现不匹配时，查看匹配串当前位置的字符有没有出现在模式串中 */
next = index + i - post[s[j]];
/*index 是当前的匹配串起始偏移量，i 是模式串还剩的比较字串数目，
* post [s [j]] 是所出现的第一个不匹配的字符在匹配串中的位置。
* 这样下次比较就从匹配串中出现 s [j] 的位置开始比较
*/
else next = index + 1;
if(next > LEN-strlen(p))
return -1; /* 匹配失败，无法进行下一次匹配 */
else
return next; /* 匹配失败，需要下一次匹配 */
}/*BM*/
/* 测试，匹配串 和 模式串都使用小写字符 */
int main()
{
int post [LEN]={0}; /* 辅助数组 = 字符集大小 */
char \*src="aaaabbbaababababbabb";/\*测试字符串\*/
char \*patten="aabbabb";
int i, next, index=-2, pos=0;/\*初始化索引标志\*/
for(i=0; i
index = BM(src, patten, 0, post);/\*第一次匹配，从0位置开始,获得NEXT\*/
while(!(index == -1 || index == 0)) /\*循环直到匹配成功\*/
{
next = index;
index = BM(src, patten, next, post);/\*下一次BM匹配\*/
}/\*while\*/
if(index == -1){ /\*faild\*/
printf("Match faildn");
}
if(index == 0){ /\* OK \*/
printf("the index is: %d.n", next);
}
return 0;
}/*main*/
网上搜索了一些关于 BM 算法的资料请参阅http://blog.chinaunix.net/u/11828/showart_242074.html 讲得很详细