對於KMP算法中的next數組大家估計都不是很陌生。
但是，next數組的意義好像是一知半解。不過next數組的博大精深，令我小輩唏噓。
一般的next求解：
void Get_Next(){
next[0]=-1;
int j=-1,i=0;
while(i
代碼很是簡單。
我們知道，在運行KMP算法的時候，模式串和主串失配的時候，主串不動（失配位置為i），我們就可以將模式串的失配位置j，移到next[j]位置，繼續進行匹配。從而減少了很多的不必要的匹配。
那麼next數組的具體意義在什麼地方呢？那麼為什麼當失配的時候可以將模式串的位置移到next[j]呢？
我們知道，可以移到next[j]，是因為，模式串中從第一個字符到低next[j]個字符和從第j-next[j]到第j和字符是一樣的。看下圖：
其實到這裡，我們是可以看出來的，next[i]數組的實際意義就是前i個字符前綴和後綴的最大匹配數。
那麼我們可以用這個數組來作什麼呢？？？
第一，求字串中【前綴+跟前綴相同的子串】的個數，詳細看這篇文字：點擊打開鏈接
第二，求一個字符串的最短周期。
我們知道，根據next數組的理解，next[i]就是指前i個字符串中，前綴和後綴的最大匹配數。
那麼我們可以得到結論，i-next[i]就是前i個字符的最短周期。
為什麼？？對，凡事不懂，要問為什麼。
幾個例子：
推薦做幾道題目：Hdu3746 Cyclic Nacklace點擊打開鏈接
Hdu1358 Period 點擊打開鏈接 都是又換周期的問題。
好了KMP就先了解到這裡，接下來要弄AC自動機了。
