KMP模式匹配算法背後的理論是什麼？

Question

KMP模式匹配算法的理論基礎是什麼？

我明白算法本身，但不明白Knuth，Morris和Pratt是如何發明這種算法的。

有沒有數學證明？

你能給一個鏈接嗎？

Answer 1

KMP匹配算法基於finite automata，並通過爲與該字符串匹配的自動機隱式構建轉換表工作。使用對字符串進行非常聰明的線性時間預處理來搜索，可以構建匹配自動機，然後可以在字符串上模擬自動機以線性時間進行搜索。最終結果是用於字符串匹配的線性時間算法。

構建的自動機通過爲每個已經匹配的字符串量創建一個狀態。默認情況下，轉換是這樣的，即匹配下一個字符前進到機器中的下一個狀態，並讀取無效字符轉換回開始。但是，搜索字符串的某些部分可能會共享某些重疊結構，因此會添加一些新的轉換，以便在讀取字符時使自動機恢復到較早的狀態（但不是第一個狀態）。

該算法通過Aho-Corasick算法推廣，該算法構建更復雜的自動機以便一次搜索多個字符串。

我an implementation of this algorithm on my personal site包含的算法是如何工作的，包括正確性證明，該算法背後更正式的直覺，以及如何獲得從基本原理，算法的解釋實際的細節進行了廣泛討論。我花了一段時間纔將它們放在一起，但我希望它能夠更好地瞭解該算法。

希望這會有所幫助！

Answer 2

Morris從第一原理中發現了該算法，但是由於Stephen A. Cook的原因，Knuth獨立地學習了一個定理，即可以在線性時間模擬確定性雙向下推自動機，並通過專門化提取早期版本的「KMP」模擬一個字符串匹配自動機。普拉特提高了效率。見Knuth's retelling。