本人是普通本科院校的一名大二學生，為提高自身能力特地鍛煉自己發表一些文章，題解等，
望各位大佬能夠對我這個菜鳥所做多多指正，在此謝過各位啦~~~

文章的開始，我想向KMP算法的三位創始人Knuth,Morris,Pratt致敬，如此思維之精妙，堪稱大神。

KMP算法是字符串匹配算法中一個很重要的算法，KMP算法的作用是在一個字符串中尋找子串的位置，也叫串的模式匹配。如主串s="aaabbaab",子串t(也叫模板串）="aab",要尋找aab在主串中的位置。

字符串匹配的暴力做法就是分別將兩個指針i，j指向主串和子串的第一個字符，從第一個字符開始，將兩個字符串的字符一一比對，如果不匹配，那么主串的i指針指向主串當前的下一個位置，繼續將兩個字符匹配，如果不匹配那就繼續移動i指針，如果匹配了，就將指向子串的j指針繼續往子串的下一個字符移動如果匹配，繼續執行，直到j指針遍歷完整個子串為止，如果不匹配，那么就是將指向字串的j指針重新指向子串的第一個為止，這個過程就叫回溯，繼續將主串和子串的i,j指針進行匹配，直到找到子串的位置為止。那么此時我們發現，每次我們匹配時j指針總會有一定的概率回溯，如果是非常龐大的數據，時間消耗會大大增加，那么問題來了，如何對這個步驟進行優化呢？這，就是KMP算法的魅力所在。

KMP算法主要分兩步，第一步是求next數組，第二步是進行匹配。next數組是對回溯的優化，就是說如果移動i指針，匹配之后移動j指針，不匹配時，先寫一個函數在子串中找到子串的最長公共前后綴，比如子串“aba”,最長公共前后綴的長度為2，然后最長公共前后綴為“ab”.暴力算法是不匹配時將子串的j指針移到子串的開始位置，但是KMP算法優化后是將j指針移到最長公共前后綴的后綴位置的起點繼續進行匹配，此時我們就不需要再把j指針移到起點了，就相當于和美女看不對眼，就退而求其次，但是不是退回起點。

下面是KMP算法的代碼詳解：

#include<stdio.h>#define N 100010 #define M 100010 char p[N],s[N]; int n,m;//n是子串的長度，m是主串的長度 int ne[N];//next數組 int main() {scanf("%d%s%d%s",&n,&p,&m,&s); //求next數組的過程for (int i = 1, j = 0; i < n; i++)//下標從0開始{while (j&& p[i]!= p[j]) j = ne[j-1];//求字串的next數組，j指向子串的起始位置，i指向子串的起始位置的下一個位置 if (p[i] == p[j]) j++;//如果相等，j指向子串的下一個位置 ne[i] = j;//子串中下標為i的字符前的字符串最長相等前后綴的長度為j}for (int i = 0, j = 0; i <m; i++)//i的話是遍歷一遍主串的所有字母，j是從子串每次從零開始遍歷，看能不能匹配成功，{while (j && s[i] != p[j])//j未回到起點，并且長串里的s[i]和短串里的p[j]匹配失敗{j = ne[j-1];//把j移到next[j-1]的位置。}if (s[i] == p[j ]) j++;if (j == n)//j走到子串的頭了 {//匹配成功printf("%d ", i - n+1);}}return 0;//時間復雜度為O(n) }

ne數組就是next數組，存儲的是j指針移動的下一個位置。

以下是函數詳解：

//求next數組的過程 void GetNext(vector<int>& next, const string& p) {next[0] = 0;//next數組初始化for (int i = 1, j = 0; i < p.size(); ++i)//i是表示后綴尾，j表示前綴尾以及i之前最長相等前后綴長度{while (j && p[i] != p[j])//當i和j不匹配時，j向前跳轉，當j已經跳轉到開頭時，不再跳轉，防止死循環{j = next[j - 1];}if (p[i] == p[j]) j++;next[i] = j;//下標為i的字符之前的最長相等前后綴的長度}} //KMP算法實現過程 int KMP(const string& s, const string& p) {vector<int> next(p.size(), 0);//初始化next數組GetNext(next, p);for (int i = 0, j = 0; i < s.size(); ++i){while (j && s[i] != p[j]){j = next[j - 1];}if (s[i] == p[j]) j++;if (j == p.size()) return i - p.size() + 1;//下標從1開始的話，return 后面加一，GetNext里的next數組里的for循環i初始化為2}return -1; }

這里是兩種情況，第一種是下標從1開始，第二種是下標從0開始。所以寫法上會有所不同。i指向主串的當前位置，j指向子串的當前位置。

這里對應leetcode第28題，實現strStr():

力扣

實現?strStr()?函數。

給你兩個字符串?haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串出現的第一個位置（下標從 0 開始）。如果不存在，則返回??-1 。

代碼如下：

void GetNext(vector<int>& next,const string& p) {next[0]=0;for(int i=1,j=0;i<p.size();++i){while(j&&p[i]!=p[j]) j=next[j-1];if(p[i]==p[j]) j++;next[i]=j;} } class Solution { public:int strStr(string haystack, string needle) {if(needle.size()==0) return 0;//重點，needle可能為空。vector<int> next(needle.size(),0);GetNext(next,needle);for(int i=0,j=0;i<haystack.size();++i){while(j&&haystack[i]!=needle[j]) j=next[j-1];if(haystack[i]==needle[j]) j++;if(j==needle.size()) return i-needle.size()+1;}return -1;} };

比上面的代碼多了一步判斷，就是說needle字符串有可能為空，此時要多考慮一種情況。

多做算法題可以讓我們的思維更縝密，更靈活。正所謂讀萬卷書，行萬里路。我們不能改變過去，但是我們可以把握當下，展望未來。

總結

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

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