?詳細(xì)理解看這里：http://kb.cnblogs.com/page/176818/

?　　　或者這里：http://blog.csdn.net/yutianzuijin/article/details/11954939

next[]數(shù)組的意義是“除自身外的最大重復(fù)子串”。

next數(shù)組計(jì)算：

理解了kmp算法的基本原理，下一步就是要獲得字符串f每一個位置的最大公共長度。這個最大公共長度在算法導(dǎo)論里面被記為next數(shù)組。在這里要注意一點(diǎn)，next數(shù)組表示的是長度，下標(biāo)從1開始；但是在遍歷原字符串時(shí)，下標(biāo)還是從0開始。假設(shè)我們現(xiàn)在已經(jīng)求得next[1]、next[2]、……next[i]，分別表示長度為1到i的字符串的前綴和后綴最大公共長度，現(xiàn)在要求next[i+1]。由上圖我們可以看到，如果位置i和位置next[i]處的兩個字符相同（下標(biāo)從零開始），則next[i+1]等于next[i]加1。如果兩個位置的字符不相同，我們可以將長度為next[i]的字符串繼續(xù)分割，獲得其最大公共長度next[next[i]]，然后再和位置i的字符比較。這是因?yàn)殚L度為next[i]前綴和后綴都可以分割成上部的構(gòu)造，如果位置next[next[i]]和位置i的字符相同，則next[i+1]就等于next[next[i]]加1。如果不相等，就可以繼續(xù)分割長度為next[next[i]]的字符串，直到字符串長度為0為止。

字符串匹配：

計(jì)算完成next數(shù)組之后，我們就可以利用next數(shù)組在字符串O中尋找字符串f的出現(xiàn)位置。匹配的代碼和求next數(shù)組的代碼非常相似，因?yàn)槠ヅ涞倪^程和求next數(shù)組的過程其實(shí)是一樣的。假設(shè)現(xiàn)在字符串f的前i個位置都和從某個位置開始的字符串O匹配，現(xiàn)在比較第i+1個位置。如果第i+1個位置相同，接著比較第i+2個位置；如果第i+1個位置不同，則出現(xiàn)不匹配，我們依舊要將長度為i的字符串分割，獲得其最大公共長度next[i]，然后從next[i]繼續(xù)比較兩個字符串。

?

字符串是從0開始的 Next數(shù)組是從1開始的

void GetNext(char *T){int j = 0;int Tlen = strlen(T));for(int i = 1; i< Tlen; i++){j = next[i];while (j && T[i] != T[j]) j = next[i];if(T[j] == T[i]) next[i+i] = j+1;} }

?

void KMP(char *S,char *T){int j = 0;int Slen = strlen(S);int Tlen = strlen(T);for(int i = 0 ; i < Slen; i++){while (j && S[i] != T[j]) j = next[j];if(S[i] == T[j]) j++;if(j == Tlen){j = next[j];}} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/yoyo-sincerely/p/5259952.html

總結(jié)

以上是生活随笔為你收集整理的KMP算法（快速模式匹配）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。