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