KMP算法

我們小組負責講這個。。。

---

術語與規定

為了待會方便，所以不得不做一些看起來很拖沓的術語，但這些規定能讓我們更好地理解\(KMP\)甚至\(AC\)自動機。

字符串匹配形式化定義如下：
假設文本是一個長度為\(n\)的數組\(T[1...n]\)，而模式是一個長度為\(m\)的數組\(P[1...m]\)，其中\(m<=n\)，進一步假設構成\(P\)和\(T\)的元素都是來自一個有限字母集\(\Sigma\)的字符。例如：\(\Sigma=\){\(0,1\)}或者\(\Sigma=\){\(a,b,...,z\)}。字符數組通常稱為字符串。

我們用\(\Sigma^*\)表示所有有限長度字符串的集合，該字符串由字母表\(\Sigma\)中的字符組成。特別地，長度為\(0\)的空字符用\(\varepsilon\)表示，也屬于\(\Sigma^*\)。一個字符串\(x\)的長度用\(|x|\)表示。兩個字符串\(x\)和\(y\)的連結用\(xy\)來表示，長度為\(|x|+|y|\)，由\(x\)的字符串后接\(y\)的字符串構成。

如果\(0<=s<=n-m\)，并且\(T[s+1...s+m]=P[1...m]\)（即如果\(T[s+j]=P[j]\)，其中\(1<=j<=m\)），那么稱模式\(P\)在文本\(T\)中出現，且偏移為\(s\)。如果\(P\)在\(T\)中以偏移\(s\)存在，那么稱\(s\)是有效偏移；否則，稱它為無效偏移。如圖一，\(s=3\)就是一個有效位移。根據此約定，字符串匹配問題就可以變成：對于模式串\(P\)找出所有文本串\(T\)的有效偏移。

如果對于某個字符串\(y\in\Sigma^*\)有\(x=wy\)，則稱字符串\(w\)是字符串\(x\)的前綴，記作\(w\sqsubset x\)。類似的，我們也可以定義后綴符號：若\(x=yw\)，則稱字符串\(w\)是字符串\(x\)的后綴，記作\(w\sqsupset x\)。可以看出：如果\(w\sqsubset x\)，則\(|w|<=|x|\)。特別地，空字符串\(\varepsilon\)同時是任何一個字符串的前綴和后綴。

（想一想我們為什么要引入\(\sqsupset\)和\(\sqsubset\)符號。）

如果不做特殊說明，我們約定認為\(a\)為一個字符，即長度為\(1\)的字符串。

為了使符號簡潔，我們把模式\(P\)的由前\(k\)個字符組成的前綴\(P[1...k]\)記作\(P_k\)，\(P_m=P\)，采用這種記號，我們又能夠把字符串匹配問題表述成：
找到所有偏移\(s(0<=s<=n-m)\)，使得\(P\sqsupset T_{s+m}\)。

首先，我們考慮樸素算法的操作過程

圖一展示了一個針對文本串\(T\)模式串\(P\)的的一個特定位移\(s\)。它已經匹配到了\(P_q\)，在\(q+1\)的位置與文本串\(T\)失配。

按照樸素算法的操作，我們這時應進行\(s'=s+1，q=1\)的操作，把文本串的匹配指針左移到\(s'+1\)位，模式串\(P\)匹配指針移回\(1\)位，從頭開始匹配。可這樣時間開銷是個很大的問題。

那怎么辦呢？

我們能不能不把文本串的指針向左移，而直接把模式串的匹配指針對準下一個可能的匹配位置上，即只移動模式串\(P\)呢？

答案是可以的。

別忘了我們已經匹配好了\(P_q\)，這意味著我們已經知道了\(T[s+1...s+q]=P[1...q]\)，如果能把這東西給利用起來那該多好啊！

怎么用呢？

于是，\(KMP\)算法就來了。

KMP主體

還是用圖二。

\(q=5\)個字符已經匹配成功的信息確定了相應的文本字符。已知的這\(p\)個文本字符使我們能夠立即確認某些偏移一定是無效的。就比如上面所說的\(s'=s+1\)。

KMP算法思想便是利用已經匹配上的字符信息，使得模式串的指針回退的字符位置能將主串與模式串已經匹配上的字符結構重新對齊。

什么意思？

假設我們存在這樣一個映射函數，先把它理解成一個小黑盒。當我們在模式串\(q+1\)的位置上失配時，它能跳到\(P\)串的某一位置\(k\)（注意是\(P\)串），即\(k=next[q]\)使得\(P_{k}\)與先前已匹配的\(q\)個字符的文本串不發生沖突，然后再比較\(k+1\)的位置是否與當前文本串指針匹配，如果不能，那繼續找\(next[k]\)；如果能，那就成功匹配一位，進行下一位的匹配。這樣，文本串的指針只會向右移而不會向左移。那么這個匹配程序就很好實現了。

這里直接給出偽代碼：

KMP-MATCHER(T,P)n = T.lengthm = P.lengthnext = COMPUTE-PREFIX-FUNCTION(P)//這里的next就是那個小黑盒q = 0for i=1 to nwhile q>0 and P[q+1]!=T[i]q = next[q]if P[q+1] == T[i]q = q+1if q == mprint "Pattern occurs with shift" i-mq = next[q]//匹配成功后肯定要往回走啊

這就是\(KMP\)算法的主體！

（仔細回味下）

那我們怎么求這個\(next[q]\)呢？

我們來觀察它的性質。

如圖三，根據\(q=5\)個字符已經完全匹配，那么圖中的\(P_k\sqsupset T[s+1...s+q]\)，且\(k\)是滿足此條件的最大值，我們直接可以從\(P[k+1]\)開始與文本串匹配。也就是說，這里的\(k\)就是我們要找的\(next[q]\)。
在圖四中，我們把\(P_q\)和\(P_k\)單獨拿了出來，你發現了什么？

\(P_k\sqsupset P_q\)！

可以看出\(k\)是滿足條件的最大值，也就是說：
\[ next[q]=max\{k:k<q且P_k\sqsupset P_q\} \]

為什么會是這樣呢？

我們想要直接在\(k+1\)位開始匹配，就得保證\(P_k\sqsupset T[s+1...s+q]\)，雖然我們在\(q+1\)位失配，但我們已經知道了\(P_q = T[s+1...s+q]\)，所以即有\(P_k\sqsupset P_q\)。

那為什么我們會要求\(k\)為滿足條件的最大值呢？
這里先簡單理解，\(k\)為最大值也就包含了\(k\)為更小值的情況。

那么，這個\(next\)我們就把它視為\(P\)的前綴函數。

那么，怎么來求這個\(next\)呢？

首先，我們肯定能想到一種樸素算法，這里就不細說了，因為用樸素算法還不如敲個\(O((n-m+1)m)\)的匹配算法呢。。。

那我們怎么來優化求法呢？

同樣假設，對于一個模式串\(P\)，我們已經知道了\(next[1...q-1]\)，現在，我們來計算\(next[q]\)。其中，\(next[q-1]=k\)。

引理1：當\(P[k+1]=P[q]\)時，可得\(next[q]=k+1\)。（前綴函數延續性引理）

證明：
因為：\(next[q-1]=k\) 即 \(P_k\sqsupset P_{q-1}\)。
若字符\(P[k+1]=P[q]\)，則\(P_{k+1}\sqsupset P_q\)。
所以：\(next[q]=k+1\)。
證畢。

引理2：若\(next[q-1]\)的最大候選項為\(k\)，即\(next[q-1]=k\)，則它的次大候選項為\(next[k]\)，次次大為\(next[next[k]]\)......（前綴函數迭代引理）

證明：（反證法）
若存在\(k_0\)使得\(P_{k_0}\sqsupset P_{q-1}\)且\(next[k]<k_0<k\)。
因為：\(next[q-1]=k\)，即\(P_k\sqsupset P_{q-1}\)。
又因為：\(k_0<k\)。
所以：\(P_{k_0}\sqsupset P_k\)。
即：\(next[k]=k_0\)。
這與\(next[k]<k_0\)矛盾。
所以假設不成立。
證畢。
后面的依次類推。

由前兩個引理可以看出，\(next[q]\)可能的候選項為：\(next[q-1]+1\)，\(next[next[q-1]]+1\)......而易知，\(next[1]=0\)。

于是，我們便可以高效計算\(next\)數組。

COMPUTE-PREFIX-FUNCTION(P)m = P.lengthpi[1] = 0k = 0for q=2 to mwhile k>0 and P[k+1]!=P[q]k = pi[k]if P[k+1] == P[q]k = k+1pi[q] = k

是不是和KMP-MATCHER很像？

其實，實質上，KMP算法求前綴函數的過程就是模式串的自我匹配。

為什么我們先說\(KMP\)算法的主體再談\(next\)的計算？其實這是從兩種角度出發認識\(KMP\)。講解主體的時候我們采用了假設法，這是一種十分感性的認知，比較好懂。在講解\(next\)的計算時，我們引用了一些數學思維來幫助我們更加理解\(KMP\)。大家可以看出，實質上，\(KMP\)主體和\(next\)的計算是幾乎一樣的邏輯。

至此，\(KMP\)算法原理的講解到此結束。

參考文獻

• 算法導論
• 算法進階指南
• 詳解KMP
• 剖析KMP
• 字符串匹配算法集合

轉載于:https://www.cnblogs.com/silentEAG/p/10550526.html

總結

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

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