定義問題

字符串匹配是這樣一個問題： 對于兩個包含且僅包含字母表∑中的字母的串P，T，計算出所有有效的**移進**s使得P[1..|P|] = T[s+1..s+|P|]。(|P|為P的長度)。
或者說：求出在什么位置P被T完全包含。
為了表達方便，定義m = |P|, n = |T|。P稱為模式串，T稱為匹配串。

樸素算法

樸素算法是一種顯然的方法。直接給出偽代碼：

Naive-Match (P, T)m = |P|, n = |T|for i = 1..n doif P[1..m] == T thenprint i" "

樸素算法可以看成模式串緊貼匹配串滑動，嘗試移進s = 1..n時能否匹配。大多數情況下，樸素算法已經可以解決問題。但是當數據極大（例如在很長的基因串中尋找一組基因）時，樸素算法的效率就顯得差了。因此，科學家尋找到許多種優秀的匹配算法。這是一個常用算法時間對照表。

算法	預處理	匹配
樸素算法	0	O((n-m+1)m)
Rabin-Karp	Θ(m)	O((n-m+1)m)
有限自動機	Θ(m∑)	Θ(n)
Knuth-Morris-Pratt	Θ(m)	Θ(n)

所有的字符串算法都很麻煩（畢竟蒟蒻）。其中KMP用處比較廣。在《算法導論》里KMP的介紹是以有限自動機為基礎的，然而我又看不懂，gedao了半天才大致明白KMP的思想。

KMP算法

Quote：來自 zrO matrix67 Orz

假如，A=”abababaababacb”，B=”ababacb”，我們來看看KMP是怎么工作的。我們用兩個指針i和j分別表示，A[i-j+ 1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應地變化，且j滿足以A[i]結尾的長度為j的字符串正好匹配B串的前 j個字符（j當然越大越好），現在需要檢驗A[i+1]和B[j+1]的關系。
- 當A[i+1]=B[j+1]時，i和j各加一；什么時候j=m了，我們就說B是A的子串（B串已經整完了），并且可以根據這時的i值算出匹配的位置。
- 當A[i+1]<>B[j+1]，KMP的策略是調整j的位置（減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配（從而使得i和j能繼續增加）。我們看一看當 i=j=5時的情況。
詳細內容參見 http://www.matrix67.com/blog/archives/115

個人理解

我是自己推導之后才看到上面大牛的解釋，真的非常通俗。所以看不懂的同學可以去哪里膜拜一下。kmp算法實在比較惡心，雖然代碼秘制煎蛋，不習慣推導的童鞋直接背下來就可以了。：（語言表達能力捉急）：。
ps：這里并沒有使用圖形輔助理解，個人認為這樣更有利于理解kmp匹配原理。
kmp基于一個函數π，π表示有最大的t < i使P[1..t] = P[m-t+1..m]，則t = π。或者形式化地：

π[i] = max{t | P[1..t] = P[m-t+1..m] 且 t < i}

證明一個結論，對于任意T[k-i+1..k] = P[1..i]，有：

π[i] = max{t | P[1..t] = T[k-t+1..k] 且 t < i}
用反證法，假設有π[i] < x < i使得P[1..x] = T[k-x+1..k]∵ P[1..i] = T[k-i+1..k]∴ T[k-x+1..k] = P[m-x+1..m]又 P[1..t] = T[k-x+1..k]∴ P[1..x] = P[m-x+1..m]∵ x > π[i], 根據定義，矛盾
原命題得證。

這個結論將說明kmp不會錯過正確解。

以及：

如果有s使T[k-s+1..k] = P[1..s]，
那么有T[k-π[s]+1..k] = P[1..π[s]]。
證明很簡單，根據定義等量代換即可。

這個結論將說明kmp不會找到錯誤解。

這些結論并不足以證明kmp的正確性，但是基本可以看出主要思想了。事實上，通過π可以省略許多無用的比較（基于第二個結論）。kmp匹配算法代碼如下：

void kmp_match(int l) {// l是T的長度，pL是P的長度int q = 0;// 匹配的長度for (int i=1; i<=l; i++) {while (q > 0 && P[q+1] != T[i])q = pie[q];// 無法匹配下一位，找到可以部分匹配的最大部分，或者沒有可以匹配if (P[q+1] == T[i])q++;// 下一位可以匹配if (q == pL) {// 找到printf("Shift %d >>> ", i-pL);q = pie[q];// 找下一個匹配位置}}
}

計算匹配函數π的方法：

void kmp_init() {int k = 0;pie[1] = pie[0] = 0;// 第一位不可能找到匹配for (int i=2; i<=pL; i++) {while (k > 0 && P[k+1] != P[i])k = pie[k];// 同上，自己匹配自己罷了if (P[k+1] == P[i])k++;pie[i] = k;// 記錄最長匹配}
}

所謂自己匹配自己，就是π就是找到一對最大且相等的前綴和后綴，記錄前綴出現位置。(基于定義)
kmp大概就是這樣了，多思考就可以想通。。

kmp時間復雜度分析

kmp的復雜度為Θ(n)-Θ(m)，這里用攤還分析中的聚合分析法給出一個kmp_init復雜度分析例子。我們試圖證明while循環的執行次數為O(n)。
k的初值為0，而k的值增長有且只有一個途徑：10行的k++。由于for循環一次k最多加一，n-1次循環之后k最多為n-1呢。由于π < i，因此while循環只會使k減少，且一次至少減少1。而k < n-1，所以while的循環次數為O(n)。不難得出kmp_init的復雜度為Θ(n)。用這種方法也可以得出kmp_match的復雜度為Θ(m)。

linux下裝逼代碼

裝逼專用，僅售998，到linux上看看效果吧。

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
char P[10005], T[10005];
int pL;
int pie[10005];
int readfln(char *str) {char c;int i = 0;str[0] = '\"';while (c = getchar()) {if (c!= '\n')str[++i] = c;else break;}return i;
}
void printfln(int shift,int l) {int beg = shift-5;if (shift <= 5)beg = 0;elseprintf("...");for (int i=beg+1; i<=shift; i++)putchar(T[i]);printf("\033[33m");printf("%s", P+1);printf("\033[0m");int end = shift+pL+5;if (shift+pL+5 > l)end = l;for (int i=shift+pL+1; i<=end; i++)putchar(T[i]);if (shift+pL+5 < l)printf("...");printf("\n");
}
void kmp_init() {int k = 0;pie[1] = pie[0] = 0;for (int i=2; i<=pL; i++) {while (k > 0 && P[k+1] != P[i])k = pie[k];if (P[k+1] == P[i])k++;pie[i] = k;}
}
void kmp_match(int l) {int q = 0;for (int i=1; i<=l; i++) {while (q > 0 && P[q+1] != T[i])q = pie[q];if (P[q+1] == T[i])q++;if (q == pL) {printf("Shift %d >>> ", i-pL);printfln(i-pL,l);q = pie[q];}}
}
int main() {pL = readfln(P);kmp_init();int l;while (l = readfln(T))kmp_match(l);return 0;
}

參考資料：《算法導論》

轉載于:https://www.cnblogs.com/ljt12138/p/6684390.html

總結

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

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