当前位置:主页 > 基础算法
字符串查找算法BM算法
日期:2017-12-05 浏览量:

字符串查找算法中,最著名的两个是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;

    相关文章:
    ·2017年高性能科学计算基础算法与可计算建模重大
    ·他设计的并行算法为大数据技术奠定基础
    ·人机大战人脸识别比拼复盘胜负手不在双方算法
    ·何宝宏:人工智能有三大基础力量 新数据 新硬件
    ·人工智能产品化的关键是基础架构和数据,而非
    → 特别推荐
    2017年高性能科学计算
    他设计的并行算法为
    人机大战人脸识别比
    何宝宏:人工智能有
    人工智能产品化的关
    算法基础之每周算法
    互联网真的不安全 基
    从内容生产、内容平
    示波器基础系列之十
    AI·算法·伦理:发明
    菜鸟CTO王文彬:未来
    厉害了Word谷歌!攻破
    游戏与算法的必经之
    基础算法题,求思路
    《计算机算法基础》
    → 热点TOP10
    谁“杀死”了
    万科最新大数
    中国开启“人
    无痛的增强学
    中国亟需修改
    建阳区初步完
    瓦力超级大脑
    2017年公务员基
    阿富汗一民营
    这家公司将损

    友情链接/网站合作咨询: