一、數(shù)據(jù)結(jié)構(gòu)中KMP算法

KMP算法介紹

KMP算法是一種改進的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP算法）。KMP算法是在 BF 算法基礎(chǔ)上改進得到的算法。學(xué)習(xí) BF 算法我們知道，該算法的實現(xiàn)過程就是 “傻瓜式” 地用模式串（假定為子串的串）與主串中的字符一一匹配，匹配不成功則返回到上一次與主串匹配的下一位字符進行匹配，算法執(zhí)行效率不高。

KMP算法的解決題型

KMP算法是在數(shù)據(jù)結(jié)構(gòu)中兩個字符串相互匹配衍生出來的算法。KMP算法的作用是在一個已知字符串中查找子串的位置,也叫做串的模式匹配。例如，對主串 A（“ABCABCE”）和模式串 B（“ABCE”）進行模式匹配，如果人為去判斷，僅需匹配兩次。雖然在以上字符較少的串中人為匹配很容易，但是讓計算機來匹配就相對慢一些，但是當(dāng)字符串中的字符非常多的時候，就不可能人為去匹配。所以打鐵還需自身硬，我們把這種枯燥的事以一定的算法交給計算機處理。

KMP算法相比BF算法的改進

每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時，無需回溯i指針（即無需將i指針完全退回至i-j+1），而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。

需要解決的問題：當(dāng)主串中的第i個字符與模式中第j個字符比較不相等時，主串中第i個字符（i指針不回溯）應(yīng)與模式中哪個字符再比較？—-假設(shè)從主串中第i個字符與模式中的第k個字符再進行比較

它是則呢樣來消除回溯的呢？就是因為它提取并運用了加速匹配的信息！

　　這種信息就是對于每模式串 t 的每個元素 t j，都存在一個實數(shù) k ，使得模式串 t 開頭的 k 個字符（t 0 t 1…t k-1）依次與 t j 前面的 k（t j-k t j-k+1…t j-1，這里名列前茅個字符 t j-k 非常多從 t 1 開始，所以 k < j）個字符相同。如果這樣的 k 有多個，則取最大的一個。模式串 t 中每個位置 j 的字符都有這種信息，采用 next 數(shù)組表示，即 next[ j ]=MAX{ k }。

延伸閱讀：

二、KMP算法的時間復(fù)雜度

主要由兩部分組成：預(yù)處理部分和匹配部分。

綜合考慮這兩部分，KMP算法的總時間復(fù)雜度為O(m+n)。與樸素的字符串匹配算法相比（其時間復(fù)雜度為O(mn)），KMP算法具有更高的效率，尤其在處理大量數(shù)據(jù)時。