PS：文章是轉(zhuǎn)載的 下方的微信公號不是我的 是原作者的。附上原文鏈接：字符串匹配之KMP jeliy王的博客

近日，一同學面試被問到字符串匹配算法，結(jié)果由于他使用了暴力法，直接就跪了(現(xiàn)在想想這樣的面試官真的是不合格的，陳皓的一篇文章說的很好，點擊閱讀)。字符串匹配方法大概有：BF(暴力破解法), 簡化版的BM，KMP，BM，一般情況下，大家聽說最多的應(yīng)該就是KMP算法了。之前學習過，由于時間間隔比較大，記不太清楚了，今天上網(wǎng)查了下，發(fā)現(xiàn)寫KMP的文章是不少，但是真正清晰簡潔就沒有了(july的文章太繁瑣)，所以自己就研究了一晚上，弄清楚了kmp的計算過程，也就在此分享下。

1. 如果你現(xiàn)在完全不知道KMP是個神馬玩意，請先閱讀 阮一峰 的《字符串匹配的KMP算法》。

KMP算法最難理解的是就是next數(shù)組的計算過程，在此分享下我所理解的kmp算法以及next數(shù)組的計算過程(如果看前面理論比較頭大，可以先看后面例子的計算過程，在回過頭來看理論就會釋懷)： 1. next數(shù)組的計算過程:? 申明:next數(shù)組下標從0算起,?定義next[0]=-1, next[1]=0; 模式串記為T[ ] 假如求 T中 j+1 位的next[j+1]： 將其 前一位(模式字符)的內(nèi)容與其前一位的next值(next[j])的內(nèi)容(T[next[j]])進行比較： 如果它們相等(T[j]==T[next[j]])，則next[j+1] = next[j]+1; 如果他們不相等，則繼續(xù)向前尋找，直到找到next值對應(yīng)的內(nèi)容與前一位相等為止，則在這個next值上加一； 如果直到第一位都沒有與之相等，則next[j+1] = 0;? ? ? ? ? ? 例: 有模式串 "abaababc" j=0時，next[0] = -1 ; j=1時，next[1] = 0; j=2時，t1!=t0, k=next[0]=-1, next[2]=0; j=3時，t2==t0, next[3] = next[2]+1 = 1; j=4時，k=next[3]=1, t3!=T[1], k=next[1]=0, T[3]==T[0], next[4]=next[1]+1 = 1; j=5時，k=next[4]=1, T[4]==T[1], next[5]=next[4]+1=2; j=6時，k=next[5]=2, T[5]==T[2], next[6]=next[5]+1=3; j=7時，k=next[6]=3, T[6]!=T[3], k=next[3]=1, T[6]==T[1], next[7]=next[3]+1 = 2;

?????? 2. 上述算法的實現(xiàn)：

//update 2014-04-19 10:08

void calNext(const char *T, int *next){

int n = strlen(T);

if(n<=0) return ;

next[0] = -1;

next[1] = 0;

int j=0, k=-1;

while(j<n){

if(k==-1 || T[j]==T[k]){

++j;

++k;

next[j] = k;

}

else k = next[k];

}

}

3. KMP主算法： 設(shè)置比較起始下標: i=0, j=0; 循環(huán)直到 i+m>n 或者 T中所有字符都以比較完畢 a. 如果 S[i]==T[j], 則繼續(xù)比較S和T的下一個字符; 否則 b. 將 j=next[j]， 從這位置開始繼續(xù)進行比較; c. 如果j==-1, 則將 i 和 j 分別加1, 繼續(xù)比較； 如果T中所有字符均比較完畢，則返回匹配的起始下標，否則返回-1； 4. KMP算法實現(xiàn)：

//update 2014-04-19 10:08

int kmpmatch(const char *S, const char *T){

if(S==NULL || T==NULL) return -1;

int n = strlen(S);

int m = strlen(T);

int next[m];

calNext(T, next);

int i=0, j=0;

while(i+m<=n){

for( ; j<m&&i<n&&S[i]==T[j]; ++i, ++j) ;

if(j==m) return i-m;

j = next[j];

if(j==-1){

++i;

++j;

}

}

return -1;

}

舉例： 設(shè)主串 S="ababcabcacbab", 模式 T="abcac" 按照上述方法計算得next[]={-1,0,0,0,1}

本篇文章主要關(guān)注next數(shù)組的計算及kmp主算法的實現(xiàn)。
要了解next數(shù)組是什么？
為什么要這么計算next數(shù)組?
參見下一篇文章(字符串匹配之KMP算法（續(xù)）---還原next數(shù)組 ).

如果你覺得本篇對你有收獲，請幫頂。
另外，我本人開通了微信公眾號--分享技術(shù)之美，我會不定期的分享一些我學習的東西. 你可以搜索公眾號：swalge或者掃描下方二維碼關(guān)注我
（轉(zhuǎn)載文章請注明出處:?http://blog.csdn.net/swagle/article/details/23969683 )

總結(jié)

以上是生活随笔為你收集整理的字符串匹配之KMP---全力解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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