字符串查找算法BM算法（Boyer-Moore)算法
时间：2010-07-15 来源：thewayma
字符串查找算法中，最著名的两个是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;
- }
-
-
相关阅读 更多 +
