KMP核心部分Next数组的理解

陈功

先给个一个写的很好的博客：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课，优酷上有。

新手学习中

太厉害了 数据结构我看的头都晕了哎 求功力传输啊