字符串查找算法BM算法（Boyer-Moore)算法

本文主要是介绍字符串查找算法BM算法（Boyer-Moore)算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法则往往比KMP算法快上3－5倍。

但是，最坏的情况下，BM的时间复杂度貌似也是n×n。

具体就不说了，BM算法是通过往后跳动主文本字符串来实现快速非回溯查找的，跳动的算法就是用程序中的这句来实现的，下面：

i = i + m - min(j, 1+last(p, T[i]) );

而last是一个求文本字符串中的字符在查找字符串里面出现的最后位置。

这个算法很麻烦，呵呵，可以的话百度一下。

整个代码如下：

 #include <string.h> 
int last(char *p, char c) { //找到c在p中最后匹配的位置,没有就返回－1 
    int length = strlen(p), count  = 0;
    char *pp = p + length -1;
    while (pp >= p)
    {
        if (*pp == c)
        {
            return length - count - 1;
        }
        pp--;
        count++;
    }
    return -1;
}
int min(int a, int b){
    return (a <= b) ? a : b;
}
int BM_index(char *T, char *p) {
    int n = strlen(T);
    int m = strlen(p);
    int i = m-1, j = m-1;
    while (i <= n-1)
    {
        if (T[i]==p[j])
        {
            if (j==0)
            {
                return i;
            }
            else
                i--, j--;
        }
        else {
            i = i + m - min(j, 1+last(p, T[i]) ); //往后跳，取决于最后一次匹配的字符的位置 
            j = m - 1;
        }
    }
    return -1;
}
int _tmain(int argc, _TCHAR* argv[])
{
    char *p = "woainizz!izzzzzz--zzzzut";
    int a = BM_index(p, "zzzzut"); //结果18，没有问题 
    return 0;
}
 