kmp有next和nextval的C語言,總算找到考研中關于計算KMP算法中的next數組和nextval數組...

考研中KMP算法中，如何手動求next數組和nextval數組？

首先我們要了解next數組的意義，為了實作更加高效的字元比對，next數組是用來尋找字元串數組内部的自身的一種規律，利用字元串内部的一種相似性，來優化字元串數組比對算法。是以才需要計算這麼一個next數組來幫助算法更好的實作字元串比對。

next數組的計算方式邏輯上稍微複雜，初學者可能很難看懂，是以首先要了解，為什麼要計算next數組以及更加優化的nextval數組。 假如有這樣一串字元串 1 2 3 4 5 6 a a a a a a 這可以說是一個字元串間規律最強的一個數組了吧，讓我們來手動模拟一下。

首先預設第一位是0，第二位是1，從第3位開始求，比較第3-1位和next[3-1]的字元是否相同，若相同，則next[3]=next[2] 1 是以第3位的值就是2.那麼依此類推就可以得到，這個字元串的next數組為 1 2 3 4 5 6 a a a a a a 0 1 2 3 4 5 總結來看就是相同就在他的next數組值加1. 那麼有這樣一個字元串那 1 2 3 4 5 6 a b c d e f 預設給出第1位為0 第二位為1 ，發現全都不一樣,可以說毫無相關性了，是以next數組為 1 2 3 4 5 6 a b c d e f 0 1 1 1 1 1

這兩種極端情況可以讓大家初步了解一下計算next數組的方法，起碼可以初步了解一下next數組的意義。但是這還不完善。 下面介紹一到北郵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數組的手動計算方法。

接下來介紹如何根據next數組計算nextval數組 nextval是在next數組的基礎上優化算法，避免不必要的浪費。其實我也不太了解nextval的具體原理，現隻能介紹一下如何計算。 依舊用上面北郵的真題為例，其真題本身求的就是nextval數組 現在我們已經有了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 現在通過next數組計算nextval數組，nextval數組與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位比較，相同，則繼續，第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數組值就是，讓第n位字元和第next[n]位比較，不同，則nextval[n]=next[n],如果相同，則比較第next[next[n]]位和第next[n]位比較，如果不同，則nextVal[n]=next[next[n]].就是這樣的計算方式。