模式匹配之Boyer-Moore算法的详细介绍
BM 算法是一个较优的模式匹配算法。一般，如果不考虑模式串的长度，一个具有时间复杂度O(n)的算法应该是最优的了，但是事实不是如此。BM算法可以实现更高效率的模式匹配。分析和实验说明，BM匹配算法对于那些字符集比较大，而模式串中出现的字符比较少的时候，工作效率最快。而且，考虑KMP匹配方式的优化，可以结合KMP匹配和BM匹配，进一步提高效率。
算法的关键和 KMP 类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数组大小只和匹配串的字符集大小相关（一般情况下也就是ASCII字符集，256个字符），其内容和模式串相关，辅助数组的内容即是模式串的索引：position[patten[i]]=i; 也是相当简单的辅助数组构造。
一个简单的例子：
#include <string.h>
#include <stdio.h> #include <stdlib.h>/* 辅助数组，取决于字符集和，默认的采用 ASCII字符集，256个元素*/
#define LEN 256 int BMMatcher(char *s, char *p, int index, int position[]) /* 参数说明： char *s： 匹配串 char *p： 模式串 int index：模式串匹配的起始位置，是匹配串的索引 int position[]辅助数组， */ { int len = strlen(s); int i,j, nextindex; i = strlen(p)-1; j = index+strlen(p)-1; for(; i>=0; i--, j--) { if(s[j] != p[i])break; } if(i<0) return 0; /*匹配成功*/ else if(position[s[j]]>0)nextindex = index + i - position[s[j]]; else nextindex = index + 1; if(nextindex > LEN-strlen(p)) return -1; /*匹配失败，无法进行下一次匹配*/ else return nextindex; /*匹配失败，需要下一次匹配*/ }/*测试， 匹配串 和 模式串都使用小写字符*/
int main() { int position[LEN]={0}; /*辅助数组*/ char *src="it is just a test, what would you do?"; /*匹配串*/ char *patten="what would"; /*模式串*/ int i, nextindex, index=-2, pos=0; for(i=0; i<strlen(patten); i++) /*构造辅助数组，关键的一步，但是很简单*/ position[patten[i]]=i; index = BMMatcher(src, patten, 0, position); while(!(index==-1 || index==0))/*循环匹配，直到匹配成功，或者匹配失败结束*/ { nextindex = index; index = BMMatcher(src, patten, nextindex, position); } if(index == -1) printf("Can not find it/n"); if(index == 0) printf("Find it, the index is: %d./n", nextindex); system("PAUSE"); return 0; }