數(shù)據(jù)結構中講到關于字符串匹配算法時，提到樸素匹配算法，和KMP匹配算法。

樸素匹配算法就是簡單的一個一個匹配字符，如果遇到不匹配字符那么就在源字符串中迭代下一個位置一個一個的匹配，這樣計算起來會有很多多余的不符合的匹配做了冗余的比較。假設源字符串長n，字串長m 該算法最差時間復雜度為 m*(n-m+1)，記為O(n*m);這里不做過多解釋樸素匹配算法。

KMP算法：

kmp算法不是在源字符串中下手，他是從字串下手，比如我要在源字符串(acabaabaabcacaabc)中匹配一個字符串字串(abaabcac)，那么從字串abaabcac下手，分析字串時，需要借助于一個數(shù)組存儲字串中存在頭字串和尾字串對稱相等的子串長度，例如?abaabcac，

a ?next[0] = -1，規(guī)定第一個字符對應的next值為-1；

ab next[1] = 0; 因為針對字符b而言，其前邊字符串a 不存在頭字串和尾字串對稱，所以為0；

aba next[2]=0 ; 因為針對子串 ab ,不存在頭字串和尾字串對稱，所以為0；

abaa next[3]=1 ; 因為針對子串aba ,存在 頭子串a和尾子串a對稱相等，其長度為1，所以為1；

abaab next[4]=1;?因為針對子串abaa ,存在 頭子串a和尾子串a對稱相等，其長度為1，所以為1；

abaabc next[5]=2;?因為針對子串abaab ,存在 頭子串ab和尾子串ab對稱相等，其長度為2，所以為2；

abaabca next[5]=0;?因為針對子串abaab ,,不存在頭字串和尾字串對稱，所以為0；

abaabcac?next[6]=1;?因為針對子串abaabca,存在 頭子串a和尾子串a對稱相等，其長度為1，所以為1；

?總結起來如下：

　　

J 0 1 2 3 4 5 6 7 P a b a a b c a c next(j) -1 0 0 1 1 2 0 1

獲取next數(shù)組的代碼如下

//獲取模式匹配字符串的next數(shù)組 void getNext(char *str,char *next) {int j = 0;int k = -1;int length = strlen(str);next[0] = -1;while(j<length){if(k == -1 || str[j] == str[k]){j++;k++;next[j] = k;}else k = next[k];} }

然后在匹配的過程中，如果遇到不匹配現(xiàn)象時，從不匹配位置分析，其next[i]的值標記著有n個頭子串和尾子串相等，即直接從next[i]的值為下標開始尋找匹配。復雜度為O(m+n) ? KMP實現(xiàn)代碼：

//src為要匹配的字符串，pat為字符串模型 int KMP(char *src,char *pat) {char next[100];getNext(pat,next);int lengthP = strlen(pat);int lengthS = strlen(src);int posS=0,posP=-1;bool flag = false;while(posS < lengthS && posP < lengthP){if (posP==-1 ||src[posS] == pat[posP]){if (flag)posS++;posP++;}else{posP = next[posP];flag = true;}}if (posP<lengthP)return -1;else return posS-lengthP; }

?

完整的代碼：

?

#include<stdio.h> #include<string.h>//獲取模式匹配字符串的next數(shù)組 void getNext(char *str,char *next) {int j = 0;int k = -1;int length = strlen(str);next[0] = -1;while(j<length){if(k == -1 || str[j] == str[k]){j++;k++;next[j] = k;}else k = next[k];} }//src為要匹配的字符串，pat為字符串模型 int KMP(char *src,char *pat) {char next[100];getNext(pat,next);int lengthP = strlen(pat);int lengthS = strlen(src);int posS=0,posP=-1;bool flag = false;while(posS < lengthS && posP < lengthP){if (posP==-1 ||src[posS] == pat[posP]){if (flag)posS++;posP++;}else{posP = next[posP];flag = true;}}if (posP<lengthP)return -1;else return posS-lengthP; } int main() {char src[100];char pat[50];printf("請輸入要匹配的字符串和字符串模板（字串）：\n");scanf("%s%s",src,pat);int f = KMP(src,pat);printf("在元字符串中匹配位置的下標為 %d ",f);return 0; }

?

總結

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

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