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

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

更新时间:2017-05-24      作者:丁老师       阅读:771

在文本内容中,都是以字符串的方式来表示,此时要精确搜索文本中是否存在目标文本,也即是搜索在大字符串中搜索目标字符串。这种精确匹配在计算机系统中有着较为广泛的应用,如文本编辑,拼写检查,情报搜索,互联网搜索等。

较为常见的字符串精确匹配算法有以下几种:

1,BF算法

BF即英文Brute Force 算法是算法模式匹配中最简单,最直观的算法。该算法的基本思想是从主字符串T(t0,t1,t2,t3,….tn-1)中的第m个字符起和目标第1个字符比较,如果相等,则继续逐个比较后续字符;比较过程中一旦发现不相等,则回溯到源字符串的m+1个字符,重新匹配,依次类推,知道目标字符串每个字符和源字符串的一个连续的字符序列相等,就匹配成功,否则匹配失败。

2,MP算法

MP算法是对BF算法的极大改进,利用了已经得到的并且存贮的比较结果,在后续比较过程中直接调用这些比较结果,大大的提高了算法的效率。在MP算法中,,最为关键的是寻找匹配失效函数,而一旦目标字符串给定,不管源字符串的取值如何,失效函数均为同一个,也即是失效函数与源字符串无关。

下面给出目标字符串的失效函数C语言代码实现方法:

voidpreMP(const char *dest, intm,intmpnext[])

{

        inti, j;

        i=0;

        j=mpnext[0]=-1;

        while(i<m)

       {    

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

                     j=mpnext[j];

               mpnext[++i]=++j;

       }

}

其中函数的参数说明如下:

dest:目标字符串

m:目标字符串的长度

mpnext:用来存贮失效发生时下一轮比较的目标字符串的起始比较位置。

在线报名

志盟科技上海招聘

在线报名 联系我们

志盟科技深圳招聘

在线报名 联系我们

志盟科技北京招聘

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

咨询热线:

咨询 QQ:517578         

就业学员

  • 就业学员

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

  • 就业学员

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

  • 就业学员

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

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

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

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

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

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