学习
实践
活动
工具
TVP
写文章

对KMP算法中next数组的深入理解

这几天在练车,所以没有每天更新,主要是练车练得有点心累,前天就已经复习完字符串这一章了,但是一直拖到今天才把KMP算法真正地弄懂。下面进入正题:

首先了解kmp算法是干嘛的,它的作用是进行一个模式匹配,即在一个字符串中寻找是否存在某一个子串,比如在aabbccabc这个主串中是否存在abc这个模式串,并且输入他们匹配时,在主串的位置,如上例中,就应该输出的是“在第7个位置他们进行匹配”。 这就是kmp算法的作用。

kmp算法的最大特点是,它不用将主串中的已经匹配过的字符进行回退(这里是和经典算法进行比较,经典的匹配情况,我们大家应该都能想到,就是在两个字符串进行比对的过程中,主串第1位和模式串第1位比较,主串第2位和模式串第2位比较,依次类推,假设主串的第i位与模式串对应位置不匹配时,那么,经典的做法就是从主串的第二位开始,再与模式串的第一位进行比较。这样依次下去,时间复杂度为o(mn),即是一个积)而kmp算法,通过使用已经匹配的位置信息,来使时间复杂度减小到O(m+n)。而在kmp算法中最关键的就是next数组的计算。 下来给出我的思路:

next[j]=k,它的意思是,当模式串的第j位与主串的第i位失配时,这时主串的位置不回退,而是将模式串退到第k位,再次与主串的第i位进行匹配。 直到成功匹配,或者超出字符数量为止。

至于为什么要这样做,我就不详细说了,严蔚敏老师的书上讲的很清楚,我想讲一下next数组代码的具体实现:(纯手敲,训练感觉)

那么上面的while循环到底是什么意思呢?实际上,kmp算法其实就是在主串与模式串失配是,在模式串中,找到最大的相同前缀和后缀。怎样找呢? 将模式串看成既是主串又是自己的模式串,

实际上,严蔚敏老师的书上已经说的很清楚了,用递归的思想来求,定义next[1]=0,我们假设next[j]=k,也就是说,第j位失配时,用第k位来进行匹配。那么第j+1位呢?有两种情况,一是当j=k时,显然,next[j+1]=k+1,二是当j!=k时,next[j+1]=next[k]+1。 看到这里不知道大家明白了没有,实际上,上面的while就是可以将这个递归的意思表达出来,至于while中为什么要加k==0,现在应该很清楚了吧,既然是递归,你必须要有一个初始条件吧,类比于数学归纳法。

**如果像上面那么说,还没懂的话,可以看看这段代码来源于这个博客

将next数组理解了之后,就很容易理解KMP算法本身了。

这里j==0,可以有两种理解,一是kmp算法的特性,二是用了next数组。

KMP算法总代码

实现示意图:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180723G1XEH900?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券