字符串匹配之KMP—全力解析

字符串匹配之KMP—全力解析

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

近日,一同学面试被问到字符串匹配算法,结果因为他使用了暴力法,直接就跪了(如今想想这种面试官真的是不合格的,陈皓的一篇文章说的非常好,点击阅读)。字符串匹配方法大概有:BF(暴力破解法), 简化版的BM,KMP,BM,普通情况下,大家听说最多的应该就是KMP算法了。之前学习过,因为时间间隔比較大,记不太清楚了,今天上网查了下,发现写KMP的文章是不少,可是真正清楚简洁就没有了(july的文章太繁琐),所以自己就研究了一晚上,弄清楚了kmp的计算过程,也就在此分享下。

1. 假设你如今全然不知道KMP是个神马玩意,请先阅读 阮一峰《字符串匹配的KMP算法》

KMP算法最难理解的是就是next数组的计算过程,在此分享下我所理解的kmp算法以及next数组的计算过程(假设看前面理论比較头大,能够先看后面样例的计算过程,在回过头来看理论就会释怀):

     1. next数组的计算过程: 
          申明:next数组下标从0算起, 定义next[0]=-1, next[1]=0; 模式串记为T[ ]
          假如求 T中 j+1 位的next[j+1]:
          将其 前一位(模式字符)的内容与其前一位的next值(next[j])的内容(T[next[j]])进行比較:
               假设它们相等(T[j]==T[next[j]]),则next[j+1] = next[j]+1;
               假设他们不相等,则继续向前寻找,直到找到next值相应的内容与前一位相等为止,则在这个next值上加一;
               假设直到第一位都没有与之相等,则next[j+1] = 0;           
           例: 有模式串 “abaababc”
          j=0时,next[0] = -1 ; j=1时,next[1] = 0;
          j=2时,t1!=t0, k=next[0]=-1, next[2]=0;
          j=3时,t2==t0, next[3] = next[2]+1 = 1;
          j=4时,k=next[3]=1, t3!=T[1], k=next[1]=0, T[3]==T[0], next[4]=next[1]+1 = 1;
          j=5时,k=next[4]=1, T[4]==T[1], next[5]=next[4]+1=2;
          j=6时,k=next[5]=2, T[5]==T[2], next[6]=next[5]+1=3;
          j=7时,k=next[6]=3, T[6]!=T[3], k=next[3]=1, T[6]==T[1], next[7]=next[3]+1 = 2;



字符串匹配之KMP---全力解析

      

     2. 上述算法的实现:
     
       //update 2014-04-19 10:08
       void calNext(const char *T, int *next){
          int n = strlen(T);
          if(n<=0) return ;
          next[0] = -1;
          next[1] = 0;
          int j=0, k=-1;
          while(j<n){
               if(k==-1 || T[j]==T[k]){
                    ++j;
                    ++k;
                    next[j] = k;
               }
               else  k = next[k];
          }
     }
     3. KMP主算法:
          设置比較起始下标: i=0, j=0;
          循环直到 i+m>n 或者 T中全部字符都以比較完成
               a. 假设 S[i]==T[j], 则继续比較S和T的下一个字符; 否则
               b. 将 j=next[j], 从这位置開始继续进行比較;
               c. 假设j==-1, 则将 i 和 j 分别加1, 继续比較;
          假设T中全部字符均比較完成,则返回匹配的起始下标,否则返回-1;
     4. KMP算法实现:

     
       //update 2014-04-19 10:08
       int kmpmatch(const char *S, const char *T){
          if(S==NULL || T==NULL) return -1;
          int n = strlen(S);
          int m = strlen(T);
          int next[m];
          calNext(T, next);
          int i=0, j=0;
          while(i+m<=n){
               for( ; j<m&&i<n&&S[i]==T[j]; ++i, ++j) ;
               if(j==m) return i-m;
               j = next[j];
               if(j==-1){
                    ++i;
                    ++j;
               }
          }
          return -1;
     }
举例: 设主串 S=”ababcabcacbab”, 模式 T=”abcac”
          依照上述方法计算得next[]={-1,0,0,0,1}


字符串匹配之KMP---全力解析



字符串匹配之KMP---全力解析


本篇文章主要关注next数组的计算及kmp主算法的实现。
要了解next数组是什么?
为什么要这么计算next数组?
參见下一篇文章(字符串匹配之KMP算法(续)—还原next数组 )

.

假设你认为本篇对你有收获,请帮顶。

另外,我本人开通了微信公众号–分享技术之美,我会不定期的分享一些我学习的东西.
你能够搜索公众号:
swalge
 或者扫描下方二维码关注我
字符串匹配之KMP---全力解析

(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/23969683 )

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118913.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • java swing 多层_java swing布局嵌套[通俗易懂]

    java swing 多层_java swing布局嵌套[通俗易懂]小菜一枚,刚接触Java,想写个注册界面,但却遇到一个奇怪问题:代码如下:publicvoidframe(){this.frame=newJFrame(“用户注册”);//窗体基本属性this.frame.setSize(600,400);this.frame.setLocationRelativeTo(null);this.frame.setVisible(true);this.fr…

    2022年10月31日
  • 51单片机入门教程(2)——实现流水灯

    51单片机入门教程(2)——实现流水灯51单片机入门教程(2)——实现流水灯一、搭建流水灯电路二、流水灯程序2.1延时程序2.2延时函数2.3按字节寻址2.4逻辑移位2.5条件判断一、搭建流水灯电路在Proteus中搭建流水灯电路如图二、流水灯程序我们可以把流水灯看作依次点亮若干个灯。程序如下:#include&amp;amp;amp;lt;reg52.h&amp;amp;amp;gt;sbitled1=P2^0;sbitled2=P2^1…

  • AVX2 初探

    AVX2 初探Intel最近发布了AVX-512,据说对浮点运算有很大提升,我的机器目前不支持AVX-512,但是支持AVX2,按照之前Intel给出的数据,据说能提速将近8倍:IntroductiontoIntel®AdvancedVectorExtensions测试环境可能这篇文章有点偏老,我这边也想验证一下没有优化的C/C++浮点运算和AVX2优化后的浮点运算到底快多少。这是我机器的配置:Manufacturer GenuineIntelName IntelCorei77820

  • sap 获取计划订单bapi_PP 常用bapi

    sap 获取计划订单bapi_PP 常用bapiBAPI:在SAP中可以允许使用BAPI访问标准功能,这些接口可以由外部应用程序开发的客户和配套软件的合作伙伴以及其他SAP应用程序使用。定义SAP业务对象类型的API方法,这些对象类型范围内的业务框架,用于基于对象的组件之间的通信。业务对象和他们的BAPI使面向对象是公司在中央信息处理。例如,现有的功能和数据可重复使用,无故障的技术可以实现的互操作性和非SAP组件可以实现。应用程序可以使用BAP…

  • 根据IP定位用户所在城市信息

    根据IP定位用户所在城市信息

    2021年10月17日
  • PHP工厂模式学习「建议收藏」

    PHP工厂模式学习「建议收藏」PHP工厂模式学习目录PHP工厂模式学习介绍引入定义参与者工厂方法模式实例工厂方法模式的优点工厂方法模式缺点适用环境小结介绍工厂方法模式,可以更好的处理客户的需求变化。引入简单工厂模式把实例化对象的工作推迟到了专门的工厂类中。但是当客户需求出现变化的时候,我们不仅得增加新的类和修改工厂类以适应客户的需求,这是设计模式所不允许的。工厂方法模式应运而生。解决思路:那里变化,封装哪里

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号