如果你用過ctrl+F這個快捷鍵，那么你有很大的概率使用過這個算法，這就是在待查找字符串（可能有成千上萬個字符）中找出模式串（比較小，可能有幾個字符），可能找到大于或者等于1次的位置。例如，在ababcd中找出abc。這里介紹算法思想，只給出了第一次出現的位置。

一.算法思想

傳統算法是從匹配串第一字符開始和模式串比較，直到遇到不符合的字符，然后從匹配串的下一個字符開始，重復上面的過程。代碼如下：

void find(char t[],char p[]){int m = strlen(t);int n = strlen(p);int i,j,k;//k:匹配串下標，j：模式串下標for(k=0;k<m;k++){j = 0;i = k;while(j<n){if(p[j]==t[i]){i++;j++;}else{break;}}if(j==n){printf("在%d處匹配\n",k);break;}} }

?

?KMP算法是這中算法的改進，在于不是i不是每次都移動一個位置，而是盡可能多的向后移動從而提高匹配效率。到底移動多少個位置，這就是KMP算法的關鍵。KMP算法維護了一個和模式串長度相同的數組，這個數組表示當前匹配到底最大前綴長度。比如abacab的最大前綴長度就是2，分別是前綴ab，后綴ab。而數組next就是[0,0,1,0,1,2]，可以利用這個信息直接跳過已經匹配到的前綴。

二.算法實現

?

void makeNext(char p[],int next[]){int q,k;//k是最大前綴長度，q是匹配串下標next[0] = 0;for(q=1,k=0;q<strlen(p);q++){//若果不相等，那么就從上一次個字符串最長前綴處查看，依次類推while(k>0&&p[q]!=p[k]){k = next[k-1];}if(p[q]==p[k]){k++;}next[q] = k;} } void kmp(char t[],char p[]){int next[3] = {0};makeNext(p,next);int i=0,j=0;//i是匹配串的下標，j是模式串的下標while(i<strlen(t)&&j<strlen(p)){//如果相等就繼續比較if(j==0||p[j]==t[i]){i++;j++;}else{//不相等就要跳躍j = next[j-1];}}if(j>=strlen(p)){printf("模式串匹配在%d處\n",i-j);}else{printf("匹配失敗了");} }

http://www.cnblogs.com/bdbk/p/5202482.html

?

總結

以上是生活随笔為你收集整理的字符串查找KMP算法（转）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。