KMP算法是壹種改進的字符串匹配算法，由D.E.Knuth、J.H.Morris和V.R.Pratt提出，所以人們稱之為Knut-Morris-Pratt運算(簡稱KMP算法)。KMP算法的核心是利用匹配失敗後的信息，最小化模式串與主串的匹配次數，以達到快速匹配的目的。KMP算法的時間復雜度為O(m+n)。
首先想到的壹定是簡單的方法，從每個元素開始，但是復雜度可以達到O(m*n)坐在不友好的數據下，壹定會騰飛。那麽如何優化呢？思考簡單練習中重復的內容？舉個例子來理解:模式字符串:abcabc，文本字符串:abcabdababcabc。
先簡單思考，後探索...abcab。下壹個c和d不匹配，那麽根據簡單算法，是不是應該向右重新開始匹配？
但是仔細看，在搜索到的abcab中，只有向右移動3步，也就是移動到最後壹個ab，才能繼續匹配嗎？然後錄同壹個前綴abc，這樣可以直接從上壹個abc跳到下壹個。這是KMP思想的精髓。匹配失敗後，我們不會壹步壹步的往回搜索，而是在搜索的過程中找到壹個公共後綴，開始搜索。
KMP的時間復雜度分析:
假設m是模式串strM的長度，n是要匹配的串strN的長度。O(m+n)+O([m，2m]+[n，2n])=計算下壹個數組的時間復雜度+遍歷比較的復雜度。也就是說，計算下壹個數組時的比較次數在[m，2m]之間。遍歷比較的比較次數在[n，2n]之間，最壞的情況是T =“AAAABAAAAB”和P =“AAAAA”。所以算法的時間復雜度是O(m+n)。
這裏分析如何得到[n，2n]的最壞情況。可以抽象地理解，在遍歷待匹配的字符串strN時，比較strN[i]和strM[j]時可能出現的情況如下:
1.當前字符匹配時，同時移動i++和j++。2.如果當前字符不匹配且j=0，則只移動i++，j=0不移動。3.當前字符不匹配，而J！當=0時，I不變，strM[j]最多彈跳j次，但j由匹配的case 1決定，case 1不可能總是* * *超過n次，所以總彈跳不會超過n次。所以最壞情況下，i++乘以(情況1+情況2) +j反彈(情況3)=n+最壞情況n=2n。[m，2m]也可以類似證明。