鱼C论坛

 找回密码
 立即注册
查看: 2530|回复: 1

[技术交流] KMP核心部分Next数组的理解

[复制链接]
发表于 2014-5-15 15:36:55 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 陈功 于 2014-5-16 09:36 编辑

先给个一个写的很好的博客:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html以下是我的一些想法:
文中(==或者=表示两个字符相等,!=表示两个字符不相等)
Next = k;
表示p1 .......... p(i-1)字符串中有前缀和后缀有长度为k-1的对称字符串,即
p1....p(k-1) = p(i-k+1)....p(i-1)
其中p1 = p(i-k+1);
        p2 = p(i-k+2);
        .......
        p(k-1) = p(i-1)
那么Next[i+1] = ?
如果有p(k) = p(i),即表示有k个字符相同,那么
Next[i+1] = k + 1=Next + 1;

如果p(i) != p(k)时,那么Next[i+1]这个值最大也就为k,所以我们要找到一个k'值使得在字符串p(1).......p(i)
中有p(1)....p(k') = p(i-k'+1)....p(i);
怎么找?
为了找到最大对称字符串p(1)....p(k')(前缀) = p(i-k'+1)....p(i)(后缀),首先要在字符串p(1).....p(k-1)中找到p(1)......p(k'-1)前缀 = p(k-k'+1).........p(k-1)后缀的最大值即对称字符串的最大值,为什么这样会成立下面会说,如何找到这个对称字符串的最大值,这时我们可以通过把模式字符串既当作主串又当作模式串,就是自己匹配自己,为什么要这样做,因为Next[k]-1这个值已知,而这个值就是p(1).......p(k-1)最大对称字符串的长度,我们只要满足Next[k]的使用条件即可。


那么什么情况下才能使用Next[k]这个值,也就是Next[k]这个值得意义是什么?
我们在模块串匹配主串时,假如模式串T[1]到T[j-1]所有已经与主串都相同了,而当S与T[j]不匹配时就把模式串把T[Next[j]]向右移动与S对齐的地方,移动的距离就是T[j]前面的字符串中最大的对称字符串的长度,也就是说移动后能保证前缀T[0].......T[Next[j]-1]与主串S之前的长度为(Next[j]-1)字符串相同的最大长度,理解这点很重要。再把T[Next[j]]与S再比较。

从上面的条件,同样的对于自己匹配自己时,我们的条件有:
1)p(1).....p(k-1) = p(i-k+1)....p(i-1) 因为Next = k;
2)p(k) != p(i);
2)Next[k] = k'的值也确定了;
所以我们可以使用Next[k]了;

p(1)..........p(k)..........p(i-k+1)................p(i-1)  p(i).................p(m)
                                  || .....|| ...... ||...... ||                                                
                               p(1)....................p(k-1)  p(k).................p(m)

把模式串移到Next[k]与p(i)对齐的位置,移动后的情况:


p(1)..........p(k)..........p(i-k+1)................p(i-1)  p(i)  p(i+1).................p(m)
                                                                                                         
                                    p(1)............p(k'-1) p(k') p(k'+1)........................p(m)
                 
p(1)......p(k'-1)前缀 = p(k-k'+1).........p(k-1)后缀.........................a
(p(1)......p(k-1)最大对称字符串的长度,等于Next[k]-1)


因为有p(1).....p(k-1) = p(i-k+1)....p(i-1)
很容易知道p(k-k'+1)........p(k-1) = p(i-k'+1)....p(i-1)....................b
由等式(a)(b)那么就有p(1)......p(k'-1) = p(i-k'+1)......p(i-1)
这样我们就获得最大对称字符串最大对称字符串   p(1)....p(k'-1)(前缀) =  p(i-k'+1)....p(i-1)(后缀)。
再比较p(k')与p(i),如果相等就获得最大对称字符串p(1)....p(k')(前缀)    =  p(i-k'+1)....p(i)(后缀),
不相等就继续通过Next[k']值来移动模式串,然后再比较。

意思就是通过移动模式串来找到p(1)......p(k'-1)前缀 = p(i-k'+1).........p(i-1)后缀的最大值,当比较不成功时,再移动模式串来找到p(1)......p(k'-1)前缀 = p(i-k'+1).........p(i-1)后缀第二大长度值,比较还不满足,就再找第三大长度值,直到比较成功。如果最后移动到只剩下p(1)=p(i-1)这一个长度时,就比较p(2)和p(i),如果还不相等,就只能比较p(1)和p(i),如果还不相等,就表示p(1)....................p(i)对称字符串长度为0。

具体过程:第一次k' = k,其实这次我们不用比较了,因为如果p(i) = p(k)的话就回到了第一种情况了就是Next[i+1] = Next + 1 = k +1;假如第二次k' = Next[k](当然这时下标j小于i+1的Next[j]都已经确定好了,因为我们是在Next已经确定的情况下讨论Next[i+1]的值;怎么确定Next的值那么就需要已知Next[i-1]的值,以此类推我们可以知道Next[k]的值已经知道了。)

假如这时p(k') == p(i)时,那么就有p(1)......p(k') == p(i-k'+1).....p(i)
那么在字符串p(1)........p(i)中有前缀p(1)......p(k')等于后缀p(i-k'+1).......p(i)这个最长对称字符串的长度为
K',而Next[j+1]的值就为p(1).....p(j)里最长对称字符串的长度+1,那么这里Next[i+1]的值就为K'+1,而K'=
Next[k],即Next[i+1] = Next[k] + 1;
在代码里的体现就为:
if(k==0 || T[k] == S){....}else{k = Next[k]}那么k = Next[k] = k',在循环到if(k ==0 ||T[k'] == S)else{....}判断语句
如果成立,就进入if语句执行k'++(=Next[k]++),i++;Next[i+1] = k'= Next[k]+1;

如果p(k')还不等于p(i),就把模式字符串(就是下面一行)向右移动Next(k')的位置,假如为k'',就有如下情况:

p(1)..........p(k)..........p(i-k+1)................p(i-1)   p(i)   p(i+1).................p(m)
                                                                                                         
                                    p(1)............p(k''-1) p(k'') p(k''+1)....................p(m)

Next[i+1]= Next[Next[k]] + 1;
终极情况:
p(1)..........p(k)..........p(i-k+1)................p(i-1)   p(i)   p(i+1).................p(m)
                                                                                                         
                                                               p(1)................................p(m)

Next[1] = 0;如果下标从1开始,从0开始就为-1;
这时如果p(i) != p(1)那么就意味着没有一个相同,即对称字符长度为0,那么Next[i+1] = Next[1] + 1 = 1;意思就是下次比较时
直接把T[1]移到到S[i+1](不再和S比较了,注意这里是最开始的目标字符串,而不是自己搞自己时的目标字符串p,别搞混了。)进行从头开始比较。
在代码里体现就为:
if(k==0 || T[k] == S){....}else{k = Next[k]}进入else语句,那么k = Next[1] = 0,再循环到if(k==0 || T[k] == S){....}else{....}判断语句
因为k == 0,进入if语句。就有了k'++(=Next[1]++),i++;Next[i+1] = k'= Next[k]+1;

如果p(i) = p(1)那么就有对称字符串长度为1,即Next[i+1] = 1(=Next[m],这里m为[2:k]区间上的某个值) + 1 = 2
表示当p[k] != p时,p(i)与p(k')进行比较,同时也意味着这在字符p(k)前面的字符串内有k'-1个字符串是相同的
p(1).......p(k'-1) = p(k-k'+1).......p(k-1);
在代码里体现就为:
if(k==0 || T[k] == S){....}else{k = Next[k]}进入if语句,就有了k'++(=Next[m]++),i++;Next[i+1] = k'= 2;
举个例子
下标     1    2    3     4    5    6     7
字符     a    b    a     b    a    a     d
Next    0    1    1     2    3    4     ?

此时i = 6,k = 4;求Next[7],很明显p(6) != p(4)        'a' != 'e'
这时就要求它的最长对称字符串,在"ababae"范围内。那么就用自己匹配自己的方式找了,这时k = 4,那么表示已经有了p(1)...p(3) == p(3)...p(5)
下标    1    2    3    4    5    6     7
字符    a    b    a    b    a    a     d
Next   0    1    1    2    3    4     ?

下标                1    2    3    4   
字符                a    b    a    b   (k' = 4)
Next               0    1    1    2
p(6) != p(4) Next[4] = 2,移动后

下标                            1    2      
字符                            a    b   (k' == 2)   
Next                           0    1  
p(6) != p(2) Next[2] = 1,来的终极情况,移动后

下标                                 1         
字符                                 a    (k' == 1)        
Next                                0   
这时p(6) == p(1),那么Next[7] = 1 + 1 = 2;  

建议看一下严蔚敏的数据结构视频第11课和第12课,优酷上有。

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-5-15 21:50:24 | 显示全部楼层
太厉害了 数据结构我看的头都晕了哎 求功力传输啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 22:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表