当前位置: 首页 >> 程序设计 >> 数据结构和算法 >> 字符串匹配之BM算法

字符串匹配之BM算法

作者：来源：louisking.cublog.cn 发表时间：2008-01-08 浏览次数：字号：大 中 小

BM算法和KMP算法一样，也是构造一个辅助的模式函数来加速匹配的速度。和KMP的模式函数相比BM的模式函数更加的简单：

void make_next(const char p[], int next[])
{
for(int i = 0; i < strlen(p); i++)
next[p[i]] = i;
}

next[] 是一个和ASCII数目一样大的数组256个数据吧。当然如果出现重复的字符，那么记录的就是这个字符最后出现的位置。

上面的这个模式函数就是，安照出现的字符对应的 ASCII 位置将 next[] 置为位置序号。

#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;//减1是因为要去掉最后的那个'\0'
   j = index+strlen(p)-1;//第一次调用 BMMatcher 时 index = 0，因为下面的 for 循环是从模式串的末尾开始比较，所以匹配串的初始比较位置应该是从开头数模式串长度个位置开始。

   for(; i>=0; i--, j--)
   {
      if(s[j] != p[i])

break;
}

if(i<0) //i<0 说明模式串已经遍历完毕

return 0; /*匹配成功*/
else if(position[s[j]]>0)//当出现不匹配时，查看匹配串当前位置的字符有没有出现在模式串中

nextindex = index + i - position[s[j]];

//index 是当前的匹配串起始偏移量，i 是模式串还剩的比较字串数目， position[s[j]]是所出现的第一个不匹配的字符在匹配串中的位置。这样下次比较就从匹配串中出现 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;
}