Boyer-Moore原理加代码

BM的提出以及动画描述过程见:
 

BM 算法是一个较优的模式匹配算法。一般，如果不考虑模式串的长度，一个具有时间复杂度O(n)的算法应该是最优的了，但是事实不是如此。BM算法可以实现更高效率的模式匹配。分析和实验说明，BM匹配算法对于那些字符集比较大，而模式串中出现的字符比较少的时候，工作效率最快。而且，考虑KMP匹配方式的优化，可以结合KMP匹配和BM匹配，进一步提高效率。

算法的关键和 KMP 类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数组大小只和匹配串的字符集大小相关（一般情况下也就是ASCII字符集，256个字符），其内容和模式串相关，辅助数组的内容即是模式串的索引：position[patten[i]]=i;  也是相当简单的辅助数组构造。

 

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LEN 256

int BMMatch(const char *src,const char *pattern,int idx,int po[])
{
    const int slen=strlen(src);
    int i=strlen(pattern)-1;
    int j=idx+i;
    
    if(j > slen)
        return -1;
        
    for(;i>=0;i--,j--){
        if(src[j] != pattern[i])
            break;
    }
    
    if(i < 0)
     {
       printf("idx is %d\n", idx);
       return 0; /* match succeed */
      }
    else if(po[src[j]] > 0) /* the charector is contained in pattern */
        idx=idx+(i-po[src[j]]);
    else /* the charector is not contained in pattern */
        idx++;
        
    return idx;
}


int BMSearch(const char *src,const char *pattern, int* nidx)
{
    int po[LEN]={0};
    int i,idx=-2;
    int plen=strlen(pattern);
   
    /* assistant array */
    for(i=0;i < plen;i++)
        po[pattern[i]]=i;
  
    /* the first time to match */
    idx=BMMatch(src,pattern,*nidx,po);

    /* start looping */
    while(idx != -1 && idx != 0){
        *nidx=idx;
        idx=BMMatch(src,pattern,*nidx,po);
    }
    
    /* return 0 or -1 */
    return idx;
}


int main(int argc, char *argv[])
{
  int ret;
  int idx = 0;
  
  ret = BMSearch("123testasadsd!","test",&idx);
  
  if(ret == 0)
    printf("finded, the index is %d\n", idx);
  else
    printf("sorry not found\n");
  
  system("PAUSE");    
  return 0;
}


 

上面的代码自己写的也很简单易懂,但是测试了下一般情况下市ok的,但是不保证觉得正确^_^.继续下一个学习了,现在时间紧迫只能不求甚解了