昨天在文章中提到了修正,沒有給出解釋.今天進行補充.讓我們先來看看我的好友寫的吧!
/////////////////////////////////////////////////////////////////////////////
程序沒有使用一個數組來保存未修正時的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://m.shnenglu.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位最好(得到休整值最好).

? 怎樣計算修正的值,就去看我同學的連接吧,寫得很清楚,不知道上面我是否寫清楚了(嘿嘿),我盡力了!!!!!