考研中KMP算法中，如何手動(dòng)求next數(shù)組和nextval數(shù)組,？
　　首先我們要理解next數(shù)組的意義,，為了實(shí)現(xiàn)更加高效的字符匹配，next數(shù)組是用來尋找字符串?dāng)?shù)組內(nèi)部的自身的一種規(guī)律,，利用字符串內(nèi)部的一種相似性,，來優(yōu)化字符串?dāng)?shù)組匹配算法。所以才需要計(jì)算這么一個(gè)next數(shù)組來幫助算法更好的實(shí)現(xiàn)字符串匹配,。
　　next數(shù)組的計(jì)算方式邏輯上稍微復(fù)雜,，初學(xué)者可能很難看懂，所以首先要理解,，為什么要計(jì)算next數(shù)組以及更加優(yōu)化的nextval數(shù)組,。 假如有這樣一串字符串 1 2 3 4 5 6 a a a a a a 這可以說是一個(gè)字符串間規(guī)律最強(qiáng)的一個(gè)數(shù)組了吧,，讓我們來手動(dòng)模擬一下。
　　首先默認(rèn)第一位是0,，第二位是1,，從第3位開始求，比較第3-1位和next[3-1]的字符是否相同,，若相同,，則next[3]=next[2] 1 所以第3位的值就是2.那么依此類推就可以得到，這個(gè)字符串的next數(shù)組為 1 2 3 4 5 6 a a a a a a 0 1 2 3 4 5 總結(jié)來看就是相同就在他的next數(shù)組值加1. 那么有這樣一個(gè)字符串那 1 2 3 4 5 6 a b c d e f 默認(rèn)給出第1位為0 第二位為1 ,，發(fā)現(xiàn)全都不一樣,可以說毫無相關(guān)性了,，所以next數(shù)組為 1 2 3 4 5 6 a b c d e f 0 1 1 1 1 1
　　這兩種極端情況可以讓大家初步了解一下計(jì)算next數(shù)組的方法，起碼可以初步理解一下next數(shù)組的意義,。但是這還不完善,。 下面介紹一到北郵2016年考研真題 1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2 這是一個(gè)考試常見的字符串，是如何計(jì)算的那,？
　　第n位：next[n]的值來自于第n-1位的字符,，通過跟第next[n-1]位字符比較，如果相同next[n]=next[n-1],如果不相同,，就跟第next[next[n-1]]位的字符比較,，就這樣迭代直到相同的時(shí)候，加上1,，如果實(shí)在沒有,，就為1. 這一段話可能很難理解，逐位分析,。 讓我們從依次來看： 第3位：第2位和第1位比較,，不相同 所以為1 第4位：第3位和第1位比較，相同,，所以為2 第5位：第4位和第2位比較,，不相同，和第1位比較,，相同,，所以為2 第6位：第5位和第2位比較， 相同,，所以為3 第7位：第6位和第3位比較,，不同，和第1位比較,，不同,，所以為1 第8位：第7位和第1位比較，相同，所以為2. 這就是next數(shù)組的手動(dòng)計(jì)算方法,。
　　接下來介紹如何根據(jù)next數(shù)組計(jì)算nextval數(shù)組 nextval是在next數(shù)組的基礎(chǔ)上優(yōu)化算法,，避免不必要的浪費(fèi)。其實(shí)我也不太理解nextval的具體原理,，現(xiàn)只能介紹一下如何計(jì)算,。 依舊用上面北郵的真題為例，其真題本身求的就是nextval數(shù)組 現(xiàn)在我們已經(jīng)有了next數(shù)組： 1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2 現(xiàn)在通過next數(shù)組計(jì)算nextval數(shù)組,，nextval數(shù)組與next相反,，是找不同， 1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2 0 1 0 2 1 3 0 2 第1位：必為0 第2位：第2位next值為1,，所以第2位和第1位比較,，不同，為第2位的next 值1 第3位：第3位next值為1,，所以第3位和第1位比較,，相同,，因?yàn)榈降?位了,，所以為0 第4位：第4位next值為2，所以第4位和第2位比較,，不同,，就為第4位next值2 第5位：第5位next值為2，所以第5位和第2位比較,，相同,，則繼續(xù)，第2位和第1位不同,，則為第2位的next值1 第6位：第6位next值為3,，所以第6位和第3位比較，不同,，就為第6位的next值3 第7位：第7位next值為1,，所以第7位和第1位比較，相同,，則為0 第8位：第8位next值為2,，所以第8位和第2位比較，不同,，則為第8位的next值2
　　【簡而言之】第n位nextval數(shù)組值就是,，讓第n位字符和第next[n]位比較，不同,，則nextval[n]=next[n],如果相同,，則比較第next[next[n]]位和第next[n]位比較，如果不同,，則nextVal[n]=next[next[n]].就是這樣的計(jì)算方式,。