boyer-moore.cpp

BM 算法是一个较优的模式匹配算法。一般

#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;
}