從《嚴書》上看到了KMP算法，看了一遍沒懂，但覺得挺神奇的，就花費了幾天時間深入的理解。
算法的原理其實不難，難的就是那個巧妙的next數組，這個next數組很吸引我，我的大部分時間也都是花費在這個數組上面的。這個next數組是KMP里面一個很關鍵的地方，對于在數據結構書上看過一遍整個算法流程的人，能夠把next數組搞明白，整個KMP算法的整體思想就差不多理解了。然后在一些細節上面深入思考一下，就可以理解和領會改進的KMP算法。
一、KMP算法簡單介紹
KMP算法是字符串匹配算法的一種，相對于樸素的字符串匹配算法而言，可以大大避免重復遍歷的情況。此算法可以在O（n+m）的時間數量級上完成字符串匹配操作。
二、神奇的next數組
關于KMP算法的原理和實現，書上或者百度一下都可以找到，我在這里就不羅嗦那么多了，直接切入主題（next數組）。
我們設主串S=abcabcabca，模式串p=abcabx。
KMP第一趟匹配：
i=6
S : a b c a b c a b c a
位置 : 1 2 3 4 5 6 7 8 9 10
P : a b c a b x
位置 : 1 2 3 4 5 6
j=6
第一次匹配到第6個位置的時候失敗了，按照樸素的算法，i要回溯到第2個位置，j要回溯到第1個位置重新匹配。KMP的話，主串中的i是不會回溯，模式串中的j回溯也不會回溯到第1個位置。注意這里是關鍵，i不用回溯就可以完成整個字符串的匹配。為什么i不需要回溯呢？我們先留下這個疑問。
我們把匹配成功的前5個字符研究一下。
1位置的前綴子串為：a , ab , abc , abca
5位置的后綴子串為：bcab , cab , ab , b
我們觀察發現兩組里面都有一個ab，你能看出點什么東西么，好的，先不管這個。
我們就按照樸素的算法來看，i回溯到第2第3位置都會在前5個字符中匹配失敗。
樸素匹配：
i=4
S : a b c a b c a b c a
位置 : 1 2 3 4 5 6 7 8 9 10
P : a b c a b x
位置 : 1 2 3 4 5 6
j=1
當回溯到第4個位置的時候，成功匹配的字符為ab，然后再去判斷S串的第6個字符和P串的第3個位置。這個然后我們先不管，觀察S中和P匹配的ab，在第一趟匹配的時候S中的ab是和P中前5個字符的最后兩個匹配的，而這一次匹配則是和P中前兩個字符匹配的。能發現點什么東西么？
不需要讓i回溯到之前的位置重新匹配，只需要找到在P串前5個字符中第一個位置的前綴子串和最后一個位置的后綴子串相等并且串長最大的那一對子串，讓j指向前綴子串最后一個字符的下一個位置3，和i所指向的6進行比較。往后遇見不匹配的時候采取和這個一樣的方法。
KMP第二趟匹配：
i=6
S : a b c a b c a b c a
位置 : 1 2 3 4 5 6 7 8 9 10
P : a b c a b x
位置 : 1 2 3 4 5 6
j=3
這個時候就需要next數組的建立了，next[6]存儲的就是前5個字符組成的字符串中的第一個位置的前綴子串和最后一個位置的后綴子串相等并且串長最大的那一對子串的最后一個字符的下一個位置，也就是3，也就是和P串中第3個位置匹配。
寫到這里，next數組應該可以得出來了。
具體代碼怎么得出來的，書上面都有。。那個應該不難。
對于next數組還有一個優化，《嚴書》上講的很清晰。
三、next數組在ACM中的應用
直接用KMP算法真的去匹配兩個字符串其實很少見，除非字符串里的字符集范圍很小，或字符重復數量過多，用KMP可大減少時間，否則一般都是直接樸素匹配。
kmp算法在ACM中并不大可能用來直接用，主要有用的是對它的理解和它的精華部分----求 next數組，這個的一個用途就是確定重復子串，具體參見 poj2406,poj1961,poj2752。
next數組模板
void get_next(string s,int next[])
{
int length=s.length();
int i=0,j=-1;
next[0]=-1;
while(i<length)
{
if(j==-1||s[i]==s[j]) /*s[i]表示后綴的單個字符*/
/*s[j]表示前綴的單個字符*/
{
++i;
++j;
next[i]=j;
}
else
j=next[j]; /*若j值不相同，則j值回溯*/
}