字符串查找算法中,最著名的两个是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;
}
责任编辑:小草