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

KMP算法介紹

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

KMP算法的解決題型

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

KMP算法相比BF算法的改進(jìn)

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

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

它是則呢樣來消除回溯的呢？就是因?yàn)樗崛〔⑦\(yùn)用了加速匹配的信息！

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

延伸閱讀：

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

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

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