什麼是KMP
三位學者發明的：Knuth，Morris和Pratt算法
KMP有什麼用
KMP主要應用在字元串比對上。
KMP的主要思想是「當出現字元串不比對時，可以知道一部分之前已經比對的文本内容，可以利用這些資訊避免從頭開始再去做比對了。」
那麼如何記錄已經比對的文本内容，是KMP的重點，也是next數組肩負的重任。
字首表
next數組就是一個字首表（prefix table）。
字首表有什麼作用呢？
「字首表是用來回溯的，意味着在某個字元失配時，字首表會告訴你下一步比對中，模式串應該跳到哪個位置。
是以字首表記錄的是模式串與主串(文本串)不比對的時候，模式串應該從哪裡開始重新比對的位置。」
為了清楚的了解字首表的來曆，我們來舉一個例子：
要在文本串：aabaabaafa中查找是否出現過一個模式串：aabaaf。
可以看出，文本串中第六個字元b 和 模式串的第六個字元f，不比對了。那如果暴力比對發現不比對，就要從頭比對了。
但如果使用字首表，就不會從頭比對，而是從上次已經比對上的内容開始比對，找到了模式串中第三個字元b繼續開始比對。
是以什麼是字首表：「下表i之前（包括i）的字元串中，有多大長度的相同字首字尾。」
驗證字首表的功能是否真如上面所說的那般強大
剛剛比對的過程在下表5的地方遇到不比對，模式串是指向f，如圖
然後就找到了下表2，指向b，繼續比對：如圖：
那麼我們通過觀察發現「下表5之前這部分的字元串（也就是字元串aabaa）的最長相等的字首 和 字尾字元串是 子字元串aa ，因為找到了最長相等的字首和字尾，比對失敗的位置是字尾子串的後面，那麼我們找到與其相同的字首的後面重新比對就可以了。」
是以字首表具有告訴我們目前位置比對失敗，跳到之前已經比對過的地方的能力。
如何計算字首表
長度為前1個字元的子串a，最長相同前字尾的長度為0。
長度為前2個字元的子串aa，最長相同前字尾的長度為1
長度為前3個字元的子串aab，最長相同前字尾的長度為0
以此類推：
長度為前4個字元的子串aaba，最長相同前字尾的長度為1。
長度為前5個字元的子串aabaa，最長相同前字尾的長度為2。
長度為前6個字元的子串aabaaf，最長相同前字尾的長度為0。
那麼把求得的最長相同前字尾的長度就是對應字首表的元素，如圖：
可以看出「字首表裡的數值代表着就是：目前位置之前的子串有多大長度相同的字首字尾。」重要重要重要
找到的不比對的位置， 那麼此時我們要看它的前一個字元的字首表的數值是多少。
為什麼要看前一個字元的字首表的數值呢，因為要找前面字元串的最長相同的字首和字尾。
前一個字元的字首表的數值是2， 是以把下表移動到下表2的位置繼續比對。
最後就在文本串中找到了和模式串比對的子串了。
字首表有什麼問題
看這個位置紅框的位置，如果要找下表1 所對應 字首表裡的數值的時候，字首表裡的數值依然是1，然後就要跳到下表1的位置，如此就「形成了一個死循環」。
「如何怎麼避免呢，就把字首表裡的數值統一減一， 開始位置設定為-1 。」 這一點對了解後面KMP代碼很重要！！
這樣就避免的死循環，隻不過後續取 字首表裡的數值的時候，要記得再+1，才是我們想要的值。
「最後得到的新字首表在KMP算法裡通常用一個next數組來表示。」
注意這個next數組就根據模式串求取的。
使用next數組來比對
有了next數組，就可以根據next數組來 比對文本串s，和模式串t了。
注意next數組是新字首表（舊字首表統一減一了）。
時間複雜度分析
再來看一下時間複雜度， 假設文本串長度為n，模式串長度為m
其中n為文本串長度，m為模式串長度，因為在比對的過程中，根據字首表不斷調整比對的位置，可以看出比對的過程是O(n)，但之前還要單獨生成next數組，時間複雜度是O(m)是以整個KMP算法的時間複雜度是O(n+m)的。
暴力的解法顯而易見是O(n * m)，是以「KMP在字元串比對中極大的提高的搜尋的效率。」