昨天在文章中提到了修正,没有给出解释.今天进行补充.让我们先来看看我的好友写的吧!
/////////////////////////////////////////////////////////////////////////////
程序没有使用一个数组来保存未修正时的NEXT值 而直接用J来充当这个功能 但是J是由NEXT（已修正）得来的 那么有没有可能J得不到正确的值？
这个问题最先是我自己想的 后来验证了一下 J一定能够得到正确的值
下面我们来分析一下
下标                         0  1  2  3  4  5  6  7  8  9 10 11 1213
目标串                     0  1  0  0  1  0  1  0  1  0  0   0   0  1
j(未修正的next)       -1 0  0  1  1  2  3  2  3  2  3   4   1  1
修正了的next          -1 0 -1  1  0 -1  3 -1 3 -1  0  4   1   0
让我们看看但模式串比较到了12位的时候（下标为11）
next[11] = 4; next[4] = 0; j|4 = 1...
这时候next[4]拿到的并不是正确的J值！！！
这会导致什么？会导致略过一个比较 即p[11]与p[1]的比较被略过！直接比较了p[11]与p[0]！
是否可以略过这个比较？！
答案是肯定的.
根据逻辑推理 如果p[11]与p[4]不等 而p[4] = p[1]那么p[11]与p[1]一定不等 所以可以略过
这样说似乎很牵强 我们再回想一下NEXT数组的意义 即当我们比较到i位时不等 应该由哪一位重新开始比较 而实际上 这个过程相当于在 7-11的这个串中查找0-3！所以根据NEXT数组的意义 我们也可以知道 这里并不会导致错误 由于被略去的比较一定不需比较 因此 J始终可以得到正确的未修正的NEXT值！
////////////////////////引用自室友 <KMP算法浅析>http://www.cppblog.com/sicheng/archive/2006/10/10/13537.html////////////

上面的例子很经典! 这里我也写点容易的,给和我一样理解能力不强的笨苯 OHOH!

看这个例子:
                     p = "aaaba"  , t = "aaabbaaaaaaaba"

                                        a  a  a  b  b  a  a  a  a  a  a  a  b  a
 
                                        a  a  a  b  a                         (第一次)

                                            a  a  a  b  a                     (第二次)

                                                              ...............

                                                                           a  a  a  b  a (成功匹配)

      1.为什么要进行修正?  我们把next数组比喻成第一次比较.  在第一次比较中,比较失败的是"第"4个字符a,这表明前4个字符是成功的!" 而p中的b的前3个字符并没有出现b",也就是说在下一趟比较中,至少应该将p向右移动4个字符;因此得到了未修正的next值=4 .
      2.而实际上,p的头个字符与最后一个字符是一样的(a).也就是说如果按照上面所说的4进行移位,再从p的头个字符开始比较同样肯定是不等的(将会出现下面的情况)
                                        a  a  a  b  b  a  a  a  a  a  a  a  b  a
 
                                        a  a  a  b  a                         (第一次)

                                                       a  a  a  b  a          (这次第一个字符a  和 第一次比较最后一个字符是一样的,因此移4位肯定也不等)

得出结论是:应该将p向右移动五位. 再从p的头个字符进行比较.

     3.所以说对于某个字符串,在算出next[i]的值后,不一定会得到"最快速的移动位数).拿上面的例子说,第2次其实移4和5位其实最后都能比较出正确答案.但移5位最好(得到休整值最好).

  怎样计算修正的值,就去看我同学的连接吧,写得很清楚,不知道上面我是否写清楚了(嘿嘿),我尽力了!!!!!