boyer-moore-hospool.txt

匹配算法

Boyer-Moore-Hospool匹配算法

这个算法在大文件中搜索小pattern有很高效率。 
推荐用来代替strstr(); 
这个实现我没有测过，不过应该不会有大问题。 
C++的代码，容易使用：） 
------------------------------------------------- 
    #include <string.h> 
    #include <assert.h> 
    #include <stdio.h> 

    class Search { 
          static const int MAXCHAR = 256; 
          int d[MAXCHAR]; 
          int m; 
          char* patt; 
    public: 
          Search(char*); 
          int find(char*); 
    }; 

    Search::Search(char* p) 
    { 
          assert(p); 

          patt = p; 
          m = strlen(patt); 

          int k = 0; 

          for (k = 0; k < MAXCHAR; k++) 
                d[k] = m; 

          for (k = 0; k < m - 1; k++) 
                d[patt[k]] = m - k - 1; 
    } 

    int Search::find(char* text) 
    { 
          assert(text); 

          int n = strlen(text); 
          if (m > n) 
                return -1; 

          int k = m - 1; 

          while (k < n) { 
                int j = m - 1; 
                int i = k; 
                while (j >= 0 && text == patt[j]) { 
                    j--; 
                    i--; 
                } 
                if (j == -1) 
                    return i + 1; 
                k += d[text[k]]; 
          } 

          return -1; 
    } 

    #ifdef DRIVER 
    int main(int argc, char* argv[]) 
    { 
          assert(argc == 3); 

          const int MAXLINE = 256; 
          char fbuf[MAXLINE]; 
          Search patt(argv[1]); 
          FILE* fp = fopen(argv[2], "r"); 
          assert(fp); 
          int nf = 0; 

          while (fgets(fbuf, MAXLINE, fp) != NULL) { 
                if (patt.find(fbuf) != -1) { 
                    fputs(fbuf, stdout); 
                    nf++; 
                } 
          } 

          fclose(fp); 

          return !nf; 
    }