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课，优酷上有。
太厉害了 数据结构我看的头都晕了哎 求功力传输啊
页:
[1]