昨天在文章中提到了修正,沒有給出解釋.今天進(jìn)行補(bǔ)充.讓我們先來看看我的好友寫的吧!
/////////////////////////////////////////////////////////////////////////////
程序沒有使用一個(gè)數(shù)組來保存未修正時(shí)的NEXT值 而直接用J來充當(dāng)這個(gè)功能 但是J是由NEXT（已修正）得來的 那么有沒有可能J得不到正確的值？
這個(gè)問題最先是我自己想的 后來驗(yàn)證了一下 J一定能夠得到正確的值
下面我們來分析一下
下標(biāo)???????????????????????? 0? 1? 2? 3? 4? 5? 6? 7? 8? 9?10 11 1213
目標(biāo)串???????????????????? 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位的時(shí)候（下標(biāo)為11）
next[11] = 4; next[4] = 0; j|4 = 1...
這時(shí)候next[4]拿到的并不是正確的J值！！！
這會(huì)導(dǎo)致什么？會(huì)導(dǎo)致略過一個(gè)比較 即p[11]與p[1]的比較被略過！直接比較了p[11]與p[0]！
是否可以略過這個(gè)比較？！
答案是肯定的.
根據(jù)邏輯推理 如果p[11]與p[4]不等 而p[4] = p[1]那么p[11]與p[1]一定不等 所以可以略過
這樣說似乎很牽強(qiáng) 我們?cè)倩叵胍幌翹EXT數(shù)組的意義 即當(dāng)我們比較到i位時(shí)不等 應(yīng)該由哪一位重新開始比較 而實(shí)際上 這個(gè)過程相當(dāng)于在 7-11的這個(gè)串中查找0-3！所以根據(jù)NEXT數(shù)組的意義 我們也可以知道 這里并不會(huì)導(dǎo)致錯(cuò)誤 由于被略去的比較一定不需比較 因此 J始終可以得到正確的未修正的NEXT值！
////////////////////////引用自室友 <KMP算法淺析>http://www.shnenglu.com/sicheng/archive/2006/10/10/13537.html////////////

上面的例子很經(jīng)典! 這里我也寫點(diǎn)容易的,給和我一樣理解能力不強(qiáng)的笨苯 OHOH!

看這個(gè)例子:
???????????????????? 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.為什么要進(jìn)行修正?? 我們把next數(shù)組比喻成第一次比較.? 在第一次比較中,比較失敗的是"第"4個(gè)字符a,這表明前4個(gè)字符是成功的!" 而p中的b的前3個(gè)字符并沒有出現(xiàn)b",也就是說在下一趟比較中,至少應(yīng)該將p向右移動(dòng)4個(gè)字符;因此得到了未修正的next值=4 .
????? 2.而實(shí)際上,p的頭個(gè)字符與最后一個(gè)字符是一樣的(a).也就是說如果按照上面所說的4進(jìn)行移位,再從p的頭個(gè)字符開始比較同樣肯定是不等的(將會(huì)出現(xiàn)下面的情況)
??????????????????????????????????????? a? a? a? b? b? a? a? a? a? a? a? a? b? a
?
????????????????????????????????????????a? a? a??b? a???????????????????????? (第一次)

???????????????????????????????????????????????????????a? a? a? b? a????????? (這次第一個(gè)字符a? 和 第一次比較最后一個(gè)字符是一樣的,因此移4位肯定也不等)

得出結(jié)論是:應(yīng)該將p向右移動(dòng)五位. 再從p的頭個(gè)字符進(jìn)行比較.

???? 3.所以說對(duì)于某個(gè)字符串,在算出next[i]的值后,不一定會(huì)得到"最快速的移動(dòng)位數(shù)).拿上面的例子說,第2次其實(shí)移4和5位其實(shí)最后都能比較出正確答案.但移5位最好(得到休整值最好).

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