陈功 发表于 2014-5-15 15:36:55

KMP核心部分Next数组的理解

本帖最后由 陈功 于 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 = ?
如果有p(k) = p(i),即表示有k个字符相同,那么
Next = k + 1=Next + 1;

如果p(i) != p(k)时,那么Next这个值最大也就为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-1这个值已知,而这个值就是p(1).......p(k-1)最大对称字符串的长度,我们只要满足Next的使用条件即可。


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

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

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与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-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值来移动模式串,然后再比较。
意思就是通过移动模式串来找到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 = Next + 1 = k +1;假如第二次k' = Next(当然这时下标j小于i+1的Next都已经确定好了,因为我们是在Next已经确定的情况下讨论Next的值;怎么确定Next的值那么就需要已知Next的值,以此类推我们可以知道Next的值已经知道了。)

假如这时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的值就为p(1).....p(j)里最长对称字符串的长度+1,那么这里Next的值就为K'+1,而K'=
Next,即Next = Next + 1;
在代码里的体现就为:
if(k==0 || T == S){....}else{k = Next}那么k = Next = k',在循环到if(k ==0 ||T == S)else{....}判断语句
如果成立,就进入if语句执行k'++(=Next++),i++;Next = k'= Next+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= Next] + 1;
终极情况:
p(1)..........p(k)..........p(i-k+1)................p(i-1)   p(i)   p(i+1).................p(m)
                                                                                                         
                                                               p(1)................................p(m)

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

如果p(i) = p(1)那么就有对称字符串长度为1,即Next = 1(=Next,这里m为区间上的某个值) + 1 = 2
表示当p != 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 == S){....}else{k = Next}进入if语句,就有了k'++(=Next++),i++;Next = 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,很明显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 = 2,移动后

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

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

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

新手学习中 发表于 2014-5-15 21:50:24

太厉害了 数据结构我看的头都晕了哎 求功力传输啊
页: [1]
查看完整版本: KMP核心部分Next数组的理解