Boyer-Moore字符串查找算法的实现

　　前段时间在园子里看到一篇讲Boyer-Moore算法原理的文章http://kb.cnblogs.com/page/176945/，写的很详细，于是在这里自己写个C语言的实现，权当是练手吧。

　　基本思路是每次从模式串的最右端开始匹配，如果后缀不匹配，模式串可以快速地后移，从而快速地匹配字符串。要用一个数组right[]，来存储失配时模式串的移动步数。数组的大小是256，即扩展的ASCII码表大小（即256个字符）。若对应字符不存在于模式串中，则赋值-1，否则表示字符出现在模式串中，查找失配时，模式串向右移动的步数。应该还有优化的空间，暂时没想了。

　　分成两个文件，一个.h文件，一个.c文件。实现中，若匹配成功则返回第一次出现模式串的位置，若不匹配则返回模式串长度。

　　N: 被搜索的字符串长度。

　　M: 模式串长度。

　　strsearch.h :

 #ifndef _STRSEARCH_H

 #define _STRSEARCH_H

 /***ASCII list length***/

 #define ASCII_LIST_LENGTH 256

 /* Interface */

 extern int BMSearch(char *dest_str,char *pattern);

 #endif

　　strsearch.c :

 #include <stdio.h>

 #include <string.h>

 #include "strsearch.h"

 #ifdef _cplusplus

 extern "C"{

 #endif

 /*

  ******Implementation of Boyer-Moore Algorithm******

  *

  * This function is to solve the string search ,and somhow we

  * can find the position of pattern string in the dest string

  * quickly.

  *

  * Copyright(c) 2013.9.6 xiaoh

  * All rights reserved.

  *

  ***************************************************

 */

 /*

  * This function is to build the jump step list for each

  * charactor.

  *

 */

 void BoyerMoore(char *pattern,int right[])

 {

     int M = strlen(pattern);

     for(int c=;c<ASCII_LIST_LENGTH;c++)

         right[c] = -;

     for(int j=;j<M;j++)

         right[pattern[j]] = j;

 }

 /*

  * Main function of Boyer-More Search Algorithm

  *

 */

 int BMSearch(char *dest_str,char *pattern)

 {

     /*Array right: steps to move for the pattern string*/

     int right[ASCII_LIST_LENGTH];

     BoyerMoore(pattern,right);

     int N = strlen(dest_str);

     int M = strlen(pattern);

     int skip; //number to jump

     for(int i=;i<=N-M;i+=skip)

  {

    　　 skip = ;

         　for(int j=M-;j>=;j--)

    　{

            　　 if(pattern[j]!=dest_str[j+i])

      　　{

   　　          　　    skip = j-right[dest_str[i+j]];//calculate the step to jump

           　　      　　if(skip<)

                   　　　　　　  skip = ;

                 　　　　break;

       　　}

    　}

        　if(skip == )

    　{

        　　　   printf("Search finished successfully.\n");

               　　return i;

    　}

   }

     printf("String cannot be found.\n");

     return N;

 }

 #ifdef _cplusplus

 }

 #endif

　　查找的最好情况时间复杂度约为O(N/M)(其实是查找完，但不匹配情况)，这里需要和O(M)比较下，如果M比较大的话N/M就比较小一些；在最坏情况下，需要比较N/M组，每组比较M次，所以时间复杂度为O(N)。其查找速度确实比KMP算法还要快。

巴特西

Boyer-Moore字符串查找算法的实现

最新文章

热门文章