C和C++文本搜索中的精确匹配算法下 - 技术分享 - 志盟培训
首页技术分享 C和C++文本搜索中的精确匹配算法下

C和C++文本搜索中的精确匹配算法下

更新时间:2017-05-31      作者:丁老师       阅读:757

MP算法之后,再一次衍生了KMP算法。KMP算法与MP算法可谓是一脉相承。

3,KMP算法核心思想是试图充分利用先前匹配过程中已经得到的结果来避免频繁回溯。也因此MP算法和KMP算法及其相似,很容易让人将MP算法和KMP算法混淆。

KMP算法的失效匹配函数C语言实现方式如下:

voidpreKMP(const char * dest, int m, intkmpnext[])

{

   inti , j;

   i=0;

   j=kmpnext[0]=-1;

   while(i<m)

  {

      while(j>-1 &&dest[i]!=dest[j])

 j=kmpnext[j];

      i++;

      j++;

      if(dest[i]==dest[j])

   kmpnext[i]=kmpnext[j];

      else

   kmpnext[i]=j;

   }

}

4,BM算法是以上搜索算法的逆向思维,在使用BM算法时,目标字符串由左向右移动,而字符的比较却是由右向左进行。当文中字符与目标字符不匹配时,则根据预先定义好的“坏字符偏移函数”和“好后缀偏移函数”计算出偏移量。

BM算法的执行过程相当复杂,但由于该算法具有很高的执行效率,在实际中应用广泛。

5,BMH算法是在BM算法上的改进算法,因在应用中,坏字符偏移函数的应用次数远远大于好后缀偏移函数次数,坏字符偏移函数在匹配过程中起着移动指针的主导作用,因此,在使用中,只是用坏字符偏移函数也非常有效。BMH是对BM算法的改进,也是一种简化,执行非常简便,而且效率也较为可观。

文本的精确匹配算法在以上的各种算法中各有优劣,据实际需要,可选择合适的算法达到最好的效果。

在线报名

志盟科技上海招聘

在线报名 联系我们

志盟科技深圳招聘

在线报名 联系我们

志盟科技北京招聘

在线报名 联系我们
联系我们

咨询热线:

咨询 QQ:517578         

就业学员

  • 就业学员

    姓名:郭凡凡 
    院校:阜阳师范学院
    就职:佳戴
    职位:软件工程师
    月薪:10000

  • 就业学员

    姓名:陈祥龙 
    院校:中北大学
    就职:美囤妈妈
    职位:软件工程师
    月薪:9000

  • 就业学员

    姓名:陈建伟
    院校:南昌航空大学
    就职:SONY
    职位:嵌入式工程师
    月薪:8000

×
×
  • *真实姓名
  • *联系手机
  • *上课地址
  •    QQ号码

温馨提示:请保持手机畅通,咨询老师将为您提供专属的一对一报名服务。

×
  • *真实姓名
  • *联系手机
  • *联系邮箱
  • * QQ号码

温馨提示:请保持手机畅通,咨询老师将为您提供专属的一对一的服务。

本站由 宽敬科技——创新企业的建站运营顾问 提供支持