<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Knuth Morris Pratt - KMP匹配算法 -------- #### 問題 在文本$$ text $$中查找字符串$$ pattern $$出現的所有位置（$$ text $$長度為$$ n $$，$$ pattern $$長度為$$ m $$，$$ n, m $$都是正整數且$$ n \gt m $$）。 #### 解法 沒有學習AC自動機前想要理解KMP算法非常困難，KMP算法可以看作只有一個模式的AC自動機的簡化版。所以將KnuthMorrisPratt放在AhoCorasickAutomata之后，請讀者在學習KMP算法之前先閱讀AhoCorasickAutomata。 將AC自動機應用在只有一個模式的匹配時，我們會發現這樣的AC自動機中沒有輸出指針，只有失敗指針。為了簡化我們不再使用樹形結構體，而用數組下標來表示失敗指針：  得到模式$$ pattern $$的每個節點跳轉的下標，在KMP算法中，這個跳轉的下標數組稱為失敗函數（Failure Function），或部分匹配表（Partial Match Table）。部分匹配表的實質也是最長后綴字符串。 當匹配到$$ text[0 \dots 3] = pattern[0 \dots 3] $$但$$ text[4] \ne pattern[4] $$時，已知$$ pattern[0 \dots 3] $$的最長后綴字符串為$$ pt[0 \dots 1] $$，按照AC自動機的算法，當前的匹配位置是$$ pattern[3] $$，沿著失敗指針$$ pattern[3] \rightarrow pattern[1] $$跳轉，然后繼續嘗試匹配$$ pattern[2] $$和$$ text[4] $$。指向前綴樹根節點的下標都設為$$ -1 $$。 由此可得，對于$$ text[i] \ne pattern[j] $$，若$$ j = 0 $$則文本上的位置右移一位$$ i = i + 1 $$，匹配上的位置不動；若$$ j \gt 0 $$則模式上的匹配位置跳轉到$$ j - 1 = pmt[j - 1] $$即$$ j = pmt[j - 1] + 1 $$，文本上的位置不動。然后繼續嘗試匹配$$ text[i] $$和$$ pattern[j] $$。對于$$ text[i] = pattern[j] $$，則文本和模式上的位置都右移一位$$ i = i + 1, j = j + 1 $$。當$$ j $$為模式$$ pattern $$的末尾字符，并且$$ text[i] = pattern[j] $$匹配成功，這時我們仍然將兩個位置右移一位$$ i = i + 1, j = j + 1 $$繼續匹配，那么顯然有$$ text[i] \ne pattern[j] $$（因為模式在這個位置已經沒有字符了），這時$$ j $$的跳轉位置為$$ j = pmt[j-1] + 1 $$，然后就可以正常匹配了。 根據AC自動機中構造前綴樹及失敗指針的算法可知： $$ (1) $$ 對于模式上的位置$$ j = 0 $$（前綴樹根節點的第一層孩子節點），其失敗指針為$$ pmt[j] = -1 $$； $$ (2) $$ 對于模式上的位置$$ j \gt 0 $$，其父節點位置為$$ j - 1 $$，父節點的失敗指針位置為$$ pmt[j-1] $$，而失敗指針的孩子節點的位置必然是$$ pmt[j-1] + 1 $$。若$$ pattern[j] = pattern[pmt[j-1] + 1] $$，則可知失敗指針為$$ pmt[j] = pmt[j-1] + 1 $$；否則失敗指針為$$ pmt[j] = -1 $$： 即公式： $$ pmt[j] = \begin{matrix} -1 & j = 0 \\ -1 & 0 \lt j \lt m, pattern[pmt[j-1]+1] \ne pattern[j] \\ pmt[j-1] + 1 & 0 \lt i \lt m, pattern[pmt[j-1]+1] = pattern[j] \end{matrix} $$ 實際編程中為了方便操作數組下標，通常會定義數組$$ next $$，令$$ next[i] = pmt[i-1] $$。 KMP算法的時間復雜度為$$ O(n + m) $$。 -------- #### 源碼 [KnuthMorrisPratt.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/KnuthMorrisPratt.h) [KnuthMorrisPratt.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/KnuthMorrisPratt.cpp) #### 測試 [KnuthMorrisPrattTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/KnuthMorrisPrattTest.cpp)