温故KMP算法

最近由于某些原因,又回顾了一次KMP算法。上一次回顾KMP算法还是在刷题的时候遇到的:

http://blog.csdn.net/dacc123/article/details/50994611

在我的记忆力,每次回顾KMP算法都会有新的理解,以为自己理解的很透彻了,等过一段时间再去回顾,又要花一些时间去弄门清。这次也一样。

刚接触Next数组的时候我很反感字符串前缀和后缀的最长公共子串的长度来解释next数组,我认为next数组就是一个字符串的对称程度。在这样的理解之下,计算next数组的理解就是:

    在求解next数组的时候,若前面一个next数,为0,那么说明前面没有对称的,新加的字符如果要对称只可能和第一个字符开始比较。如果next数不为0,说明前面一个字符是有和它对称的,那么去找和他对称的字符的下一个字符,如果相等那么next值就++,如果不相等只能等于0了。

从今天看来,这个对称理解显然是错误的,很容把误导到回文串里面的前后对称。KMP算法其实很简单,就从前缀和后缀去理解他,这也是他算法的核心思想。

下面举个例子:

第一次匹配:从第0位开始,匹配到第7位都是相同的,最后一位发现不一样了就是第8位

0   1    2   3   4   5    6   7   8

a   b   c    x   y    a   b   c   x   y   a -------------目标字符串

a   b   c    x   y    a   b   c   1     -----------------模式字符串

接下来:

如果是暴力的话,应该是模式字符串向前移动一位,进行比较,发现第一位有不匹配的继续移动。

0   1    2   3   4   5    6   7   8

a   b   c    x   y    a   b   c   x   y  a -------------目标字符串

     a   b   c    x    y   a   b   c   1     -----------------模式字符串

假设暴力移动了x位,终于有可能匹配了,这里是有可能。那么情况一定是这样:

0   1    2   3   4   5    6   7   8

a   b   c    x   y    a   b   c   x   y   a -------------目标字符串

                         a   b   c   x   y   a   b   c   1     -----------------模式字符串

模式字符串的a , b ,c和目标的5,6,7位是相同的,(我们不看第8位以及后面的只看0~7)。这样才有可能匹配(前面移动的都是从第一位就pass掉了)。

那么回到第一步:

0   1    2   3   4   5    6   7   8

a   b   c    x   y    a   b   c   x   y   a -------------目标字符串

a   b   c    x   y    a   b   c   1     -----------------模式字符串

在发现第8位不匹配的时候,我们之前暴力推算过,向前移动5位,才有可能匹配。(只看0~7位)前7位都是相同的,我们可以找到规律,为什么移动5位才有可能匹配:

a   b   c   x   y   a   b  c

                       a   b  c   x    y   a   b  c

可以看这就是一个字符串的前缀=后缀的情况,不是吗?也就是说,只有当前缀等于后缀存在的情况下,你往后移才有可能匹配(在0~7之内有匹配的)。在发现第8位不匹配的情况下,我们利用next数组,直接找到前缀=后缀的那部分,直接移动过去,这样省了很多步暴力。如果发现前缀=后缀的情况不存在,那么好办,直接跳过0~7位,因为前缀=后缀不存在,你在0~7位之间怎么移动都不可能匹配。

接下来就是利用前缀与后缀求next数组的方法,很容易理解。

比如 s: a   b    a   b 

next[i]  表示的是从第0~i位的字符串,前缀和后缀的最大公共子串的长度。求解next[i] 其实只有两种情况,一种是next[i-1]也就是0~i-1的子串存在前后缀最大公共子串,例如a  b  a  b 现在求解最后一位b也就是next[3],可以看next[2]=1 因为a b a的公共前后缀是a长度是1,s[0]=s[2]="a" 。 那么如果s[1]=s[3]的话,公共前后缀岂不是要加1,于是b就去找s[2]匹配的前缀就是s[1],找他的下一位s[1],果然和自己相等,于是在next[2]的基础上加1.。还要一种就是前面的next[i-1]没有前后缀公共子串,那么看来只有从自己开始开辟了,忽视果断和第一位比较,如果相等,那么从i开始就有了前后缀公共子串,长度为1.

这里还要提一点,next[i] 还表示和s[i]相等的前缀s[j]的下标j,s[j]是前缀的最后一个字符,s[i]是后缀的最后一个字符。s[i]=s[j] ,j的值既是下标(从0开始的要加 1)也是长度。

next[0]   a   只有一个字符串,最大公共子串长度为0

next[1]   a b   由于next[0]=0,说明前面的子串没有前后缀相等的情况,只能从自己开辟,发现s[0]和自己不一样,于是只能next[1]=0

next[2]  a b a   next[1]=0,同样的从自己开辟,发现s[0]和自己一样,终于有戏,于是next[2]=1

next[3]  a b a b    next[2]=1 ,前面有匹配的,于是找到next[2]匹配的那个字符串下表也就是next[2]的值,是1(我这里是下标从0开始)于是找s[0]的下一位s[1]发现和自己一样,很完美,在next[2]的基础上加1。如果不一样呢,那么很认命,自己破坏了前后缀公共子串,只能是0.

至于代码什么的就不贴了,明白了原理,写代码是信手拈来的事情,对吧!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

2014阿里巴巴 实习生电面题目:输出给定字符串的全部连续子串

转载请注明出处:http://blog.csdn.net/ns_code/article/details/21043665

931
来自专栏蓝天

常见指针定义解读

最近做的C/C++技术面试比较多,发现了一些共同的问题,对于如下所示的指针认识,多数面试者都答错了,作为过来人,这种情况还可以理解的,放在一起确实有些复杂。 ...

521
来自专栏醒者呆

面向程序员编程——精研排序算法

这篇文章很长,我花了好久的时间(中间公司出了bug,加班了好几天( ¯ ¨̯ ¯̥̥ ))进行整理,如有任何疑问,欢迎随时留言。 关键字:排序算法,时间...

3705
来自专栏小筱月

各种排序算法

冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序

1323
来自专栏程序员叨叨叨

8.1 函数第 8 章 函数与程序设计

通过第 5 章到第 7 章的阅读,我们已经知道了怎么声明变量(第 5 章),怎么写表达式和语句(第 6 章),怎么将输入 \ 输出参数绑定到语义词(第 7 章)...

932
来自专栏从流域到海域

Python惰性序列

Python的iterator就是一个惰性序列,要说明什么是惰性序列,首先我们得知道什么是惰性计算。 事实上,很多如Java在内的高级语言都支持惰性序...

2536
来自专栏chenjx85的技术专栏

leetcode-162-寻找峰值

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

1513
来自专栏我的技术专栏

图说C++对象模型:对象内存布局详解

2763
来自专栏小狼的世界

两个有序数组中查找第K大数

题目:两个数组A、B,长度分别为m、n,即A(m)、B(n),分别是递增数组。求第K大的数字。

1862
来自专栏Python小白进阶之旅

Python基本的排序算法比较,sorted的实现方法

简介:依次检查需要排序的列表,每次取出一个元素放入另一个排好序的列表中的适当位置。

963

扫码关注云+社区