由于KMP演算法描述起來很抽象，所以很多人難以理解，那么這篇博客將幫你解決這個難題，帶你徹底了解KMP的原理以及實作，
KMP演算法是一種改進的字串匹配演算法，KMP演算法的核心是利用匹配失敗后的資訊，盡量減少模式串與主串的匹配次數以達到快速匹配的目的，具體實作就是通過一個next陣列實作，next陣列本身包含了模式串的區域匹配資訊，演算法時間復雜度 O(m+n)
舉個栗子，如
給定一個長度為 m 的模式串 S，以及一個長度為 n 模板串 P，判斷 P 是否是 S 的字串
要想真正了解KMP演算法，首先要來研究下樸素的匹配演算法，
樸素模式匹配怎么做呢 ？
樸素的匹配其實很好理解，但為了后面更好的理解KMP演算法，這里還是需要做一下圖解
依次類推，有兩種情況發生
①
②
文字描述
步驟 1：從 S 的第一個字符開始與 P 的第一個字符比較 ，如果相等則繼續拿 S 的下一個字符開始與 P 的第二個字符比較，以此類推，如果P串達到末尾，那么 P 為 S 的字串，
步驟 2：如果出現不相等的情況，從 S 的第二個字符開始與 P 的第一個字符比較，如果相等則繼續拿 S 的下一個字符開始與 P 的第二個字符比較，以此類推，如果P串達到末尾，那么 P 為 S 的字串，
步驟 3：如果 P串沒有達到末尾，S卻先到達末尾，那么 P 則不是 S 字串
演算法實作
bool isMatch;
for (int i = 1; i + n - 1 <= m; i++) //字串從下標為1的位置開始存盤
{
isMatch = true;
for (int j = 1, k = i; j <= n; j++, k++)
{
if (s[k] != p[j])
{
isMatch = false;
break;
}
}
if (isMatch) break;
}我們可以看到樸素匹配的演算法復雜度為O( n * m)，那么有沒有辦法降低演算法復雜度呢？
觀察上述的圖解（這里是關鍵）
此時可以看到第一次不相等的地方已經標了 標注了 棕色的小豎線 | ，表示S串與P串不相等的位置
那么，如果這一次能匹配成功的話，意味著什么呢？看圖！
假設黑色部分不相等， 也就是 以 i點為結尾的頭串 不等于 以 j點末串 ，顯然這一次也不能匹配成功！那么就需要從S串的下下個位置開始比較，那如果 以 i點為結尾的頭串 等于 以 j點末串 呢？
如果等于，顯然 一直到 i點 都不需要再一次與S串比較，因為這一段已經是上一次匹配成功的了，這就是KMP的精髓所在，
那么說整個問題就變成了：只需要找到P串中 以 1~m 結尾的末串 分別和 哪一個 i 結尾的頭串相等即可， 這樣當 j+1點開始，P串與S串不相等時，只需要找到以 j點為結尾的末串 相等的 頭串 i，從頭串 i 的下一個位置開始與S串比較即可！ 用以保存這些資訊的就是 NEXT陣列，
如何預處理next陣列呢？ 只需要 用P串的 與自己比較即可，開始位置是一定相等的 P[1] ==P[1],
為了使比較次數更少，next陣列則是保存 以 j結尾 與 i開頭相等的最長位置，但顯然 i ！=j，，否則就是自身與自身相等了，沒意義，所以 P串一定要從第二個位置開始 與自身比較，
演算法實作
//構建next陣列
for(int i = 2, j = 0; i <= m; i++)
{
while(j && p[i] != p[j+1]) j = next[j];
if(p[i] == p[j+1]) j++;
next[i] = j;//每次移動 i 前，將 i 前面已經匹配的長度記錄到next陣列中
}next構建完畢，則開始 S串和P串的比較 ，方法幾乎與構建next陣列一致，因為構建next陣列是自己與自己比較，而比較S和P 則是 不同的字串比較，
演算法實作
bool isMatch=false;
for(int i=1,j=0;i<=m;i++)
{
while(j && s[i]!=p[j+1]) j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==n) //當j==n時則說明 P串最后一個字符已經和S串匹配，則P為S的字串
{
isMatch=true;
break;
}
}這么一看KMP并不復雜，讀者理解之后，熟記代碼即可，
最后感謝讀者點贊支持！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/303633.html
標籤：其他
下一篇：移動端Web開發 基礎知識