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