kmp算法時間複雜度

KMP算法是一種改進的字符串匹配算法，由h，is和t提出的，因此人們稱它爲克努特—莫里斯—普拉特操作（簡稱KMP算法）。

KMP算法的核心是利用匹配失敗後的信息，儘量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是通過一個next()函數實現，函數本身包含了模式串的局部匹配信息。

KMP算法的時間複雜度O(m+n)。

KMP算法用於判斷一個字符串是否是另一個字符串的子串。

KMP的時間複雜度是：匹配過程的時間複雜度爲O(n)，計算next的O(m)時間，兩個獨立的環節串行，所以整體時間複雜度爲O(m + n)。