除了字尾陣列計算之外，該演算法的時間複雜度是 O。 由於 GenerateSuffixArray knuthmorrispratt 採用 O，因此 knuthmorrispratt KMP 演算法的總時間複雜度為：O(m+n)。
上面的例子以最少的複雜步驟展示了組織這個表格的一般性方法。 knuthmorrispratt 這麼做的原理是對整體的搜尋：大多數工作已經在檢測到當前位置的時候做完了，剩下需要做的很少。 knuthmorrispratt 略微複雜的一點是找到一個共同前字尾。
knuthmorrispratt: Knuth-Morris-Pratt(KMP) 演算法簡介
部分匹配表，又稱為失配函式，作用是讓演算法無需多次匹配S中的任何字元。 能夠實現線性時間搜尋的關鍵是在主串的一些欄位中檢查模式串的初始欄位，可以確切地知道在當前位置之前的一個潛在匹配的位置。 換句話說，在不錯過任何潛在匹配的情況下，”預搜尋”這個模式串本身並將其譯成一個包含所有可能失配的位置對應可以繞過最多無效字元的列表。 該演算法由 Donuld Knuth和 Vaughan Pratt於 1970 年構思，由 James H. Morris獨立構思。 構建這個陣列的時間複雜度是 knuthmorrispratt O，空間複雜度也是 knuthmorrispratt O。 為了確保你是否已完全理解該演算法，請嘗試為模式 aabaabaa 生成一個陣列，並檢查結果是否與此匹配。
- 構建這個陣列的時間複雜度是 O，空間複雜度也是 O。
- 由於 GenerateSuffixArray 採用 O，因此 KMP 演算法的總時間複雜度為：O(m+n)。
- 上面的例子以最少的複雜步驟展示了組織這個表格的一般性方法。
- 換句話說，在不錯過任何潛在匹配的情況下，”預搜尋”這個模式串本身並將其譯成一個包含所有可能失配的位置對應可以繞過最多無效字元的列表。
- 部分匹配表，又稱為失配函式，作用是讓演算法無需多次匹配S中的任何字元。
- 能夠實現線性時間搜尋的關鍵是在主串的一些欄位中檢查模式串的初始欄位，可以確切地知道在當前位置之前的一個潛在匹配的位置。
