在電腦科學中，Knuth-Morris-Pratt字串尋找演算法（簡稱為KMP演算法）可在一個主文字字串S內尋找一個字W的出現位置。此演算法通過運用對這個詞在不匹配時本身就包含足夠的資訊來確定下一個匹配將在哪裡開始的發現，從而避免重新檢查先前匹配的字元。(維基百科)來講一下一般的字串搜尋，假設一個情境：
Pos: 01234
Target: aaaac
Pattern:aac
通常會逐一比對，從0開始，Target[0]對上Pattern[0]，接著[1]，[2]，匹配失敗。繼續往下，再Target[1]比Pattern[0]，繼續往下比...
這樣會有些字符會重複搜尋過，如果第二個 a 有對上，第三個配不上，因為第二個 a 對上第一個 a，所以下次搜尋應該從第一個 a 對上的後面開始。
如此一來，便能夠減少搜尋次數，提高搜尋的效率。
KMP便是一種這樣構想的演算法。
推薦教學：bilibili
這幾天碰到一個困難的題目，我開始推理，思考搜尋字串重複的可能性解法，像是0~999之間，不出現 55 跟不出現 54的次數是不相等的。
這裡不講艱深的理論，只講要如何簡單地理解並使用。
範例：Github 入門版 、 入門版2、入門簡化 、函式簡化
如果毫無基礎，也可以直接從範例入門版看起並嘗試理解，不一定要看以下解說。
沿用情境，Target = "aaaac", Pattern = "aac"。
首先要用 pattern 要建立一個前綴表 PrefixTable。目的是決定該位置匹配失敗後，該移到pattern的哪個位置繼續匹配。
因此以 aac 來說，當pattern索引到 2 時，如果在 aa「c」的位置匹配失敗，那麼 prefixTable[2] 要導向 1 ，使得接下來的搜尋去比對 a「a」c 即 pattern[1]。就不用因為一次失敗而回到pattern[0]開始。
要如何找出決定這個 PrefixTable (dict)的值？
如果今天pattern只有一個字母，當前Target位置沒有匹配到，Target位置換下一個繼續匹配。
因此pattern在第一個字母[0]時沒有匹配上，代表Target位置要換下一個位置，因此PrefixTable[0]是特別的。
「a」ac，在 [0] 位置上會是讓 Target位置換下一位的值，設為 -1 能跟其他索引有所區別。不能設為 0，因為 [0] 代表「a」ac 自身，這樣會造成無限循環。
接下來講超越長度1的部分，直接跳到 aa「c」，這裡先跳過 a「a」c不講，因為我們對 aa「c」的已經有想法。
如果 aa|a|ac <=> aa|c|匹配失敗，會希望用下一個是 aa|a|ac <=> a|a|c。
這裡有個很重要的問題，是甚麼樣的計算，決定了要回到 a|a|c 的位置？
aa：如果第一個字母為 a，第二個字母如果也是 a，前後相同，長度為1。
abab：如果前兩個字母為 ab，後兩個字母為 ab，前後相同，長度為2。
後方新加入的部分要是跟前面部分的後方相同，長度就會 +1，換句話說也等於後綴與前綴最大相同的數目。
如果前後綴有相同的部分，就能夠不用回到[0]重新開始。PrefixTable的值跟pattern前後綴最大相同的數目是相關的。
回到 aa「c」上面，如果搜索失敗，回到用 pattern[1] 匹配。而 1 也是 aa 的前後綴最大相同的數目。
決定 aa「c」回去位置的，是 c 前面的 aa 。 決定 a「a」c回去位置的，是 a 前面的 a 。
如此可以把 aac 分切成： ""、"a"、"aa"，分別對應「a」ac、a「a」c、aa「c」。
到這裡，「a」ac: -1、aa「c」: 1，而 a「a」c 對應值為 0，因為 a 沒有辦法找前後綴相同。
PrefixTable的值已經知道如何計算了，而鍵可以用 0、1、2或是 a、aa、aac都可以。
接下來要如何使用 PrefixTable 進行 KMP 搜尋呢？
Target跟Pattern的搜尋位置，各需要一個索引(index)控制，這裡稱作 TI、PI。
TI、PI預設為0，當 Target[0] 跟 Pattern[0] 相同時，兩者往下 TI +1、 PI + 1。
當 Target[0] 跟 Pattern[0] 不相同時，查 PrefixTable[0]，得 -1，因此 TI +1 往下找。
接著來到 Target[2] 跟 Pattern[2] 不相同，查 PrefixTable[2]，得 1，PI = 1
接下來 Target[2] 跟 Pattern[1] 相同，兩者往下 TI +1、 PI + 1。
這樣搜尋直到找到底，或是出現全匹配的狀況。
如果是全匹配且需要繼續搜索，此時 PI 會跟 Pattern 的長度相等，超出範圍，因此 PI -= 1，讓 Pattern 回到 PrefixTable[PI-1]處搜尋。
範例有Python的代碼，可以參考看看，然後自己從頭實踐看看。