KMP算法一直讓我們又愛又恨，難以理解卻又效率很高。

看了看網(wǎng)上的KMP教程，無論是博客還是視頻，大多以文字和邏輯推導(dǎo)的方式呈現(xiàn)，紛繁復(fù)雜，晦澀難懂。這會讓我們在初學(xué)時多走很多彎路。

人類接受知識最直觀的方式就是理解圖像。于是我嘗試用圖解的方式詳細解釋一下KMP的原理， 最后通過例題加深鞏固，達到完全學(xué)會的目的。

---

因為暴力匹配算法（BF算法）是學(xué)習(xí)KMP的前提， 因此，我們通過講解BF算法，來引入KMP算法。

串的模式匹配的概念：
顧名思義，模式串B在文本串（主串）A中的查找過程，我們稱為模式匹配。

解法一：暴力匹配算法
舉個例子：
若給定文本串

BBC ABCDAB ABCDABCDABDE

和模式串

ABCDABD

現(xiàn)在要拿模式串去跟文本串匹配，整個過程如下所示：

首先，文本串的第一個字符與模式串的第一個字符，進行比較。因為B與A不匹配，所以搜索詞后移一位。

因為B與A不匹配，搜索詞再往后移。

就這樣，直到字符串有一個字符，與搜索詞的第一個字符相同為止。

接著比較字符串和搜索詞的下一個字符，還是相同。

直到字符串有一個字符，與搜索詞對應(yīng)的字符不相同為止。

這時，我們需要將搜索詞整個后移一位，在從頭逐個比較。

經(jīng)過多次循環(huán)， 我們總能成功匹配到對應(yīng)的字串。

以上是暴力匹配算法的核心思想。

但與此同時：
一個基本事實是：當(dāng)空格與D不匹配時，你其實已經(jīng)知道前面六個字符是“ABCDAB”,而第二個字符B與目標(biāo)串的第一個字符A是肯定失配的；
因此：
KMP算法的想法是：設(shè)法利用這個已知信息，不要把“搜索位置”移回到已經(jīng)比較過的位置，轉(zhuǎn)而繼續(xù)把它向后移，這樣就提高了效率

怎么做到這一點呢？
可以針對搜索詞，算出一張部分匹配表，這張表是如何產(chǎn)生的，我們后面再做介紹，這里只要會用就可以了。


當(dāng)空格和D不匹配是，前面六個字符“ABCDAB”是匹配的。查表可知，最后一個匹配字符對應(yīng)的“部分匹配值是2”，因此按照下面的公式可算出向后移動的位數(shù)：

$$移動位數(shù)=已匹配的字符數(shù)?對應(yīng)的部分匹配值$$

因為6 - 2 = 4 ， 所以將搜索詞向后移動4位。

因為空格和C不匹配，所以繼續(xù)向后移動搜索詞，這時，已匹配的字符數(shù)為2（AB），對應(yīng)的部分匹配值為0，所以移動位數(shù)為：2 - 0 = 2 ，向后移動兩位。

因為空格與A不匹配，繼續(xù)后移一位。

逐位比較，直到發(fā)現(xiàn)C與D不匹配，于是，移動位數(shù) = 6 - 2 ，繼續(xù)將搜索詞向后移動4位。

逐位比較，直到搜索詞的最后一位，發(fā)現(xiàn)完全匹配，于是搜索完成。如果還要繼續(xù)搜索，移動位數(shù) = 7 - 0 ， 再次將搜索詞向后移動7位 ，這里就不在重復(fù)了。

下面介紹一下《部分匹配表》是如何產(chǎn)生的。

首先：了解兩個概念：前綴和后綴
前綴指除了最后一個字符以外， 一個字符串的全部頭部組合，后綴指除了第一個字符以外，一個字符串的全部尾部組合。
舉例：字符串bread的前綴和后綴如圖所示：

"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度。
以"ABCDABD"為例，

在這里，“部分匹配”的實質(zhì)就是：

有時候，字符串的頭部和尾部會有重復(fù)，比如：“ABCDAB”之中有兩個AB，那么他們的“部分匹配值”就是2，也就是向后移動時，
第一個“AB”向后移動四位，（字符串長度-部分匹配值），就可以來到第二個“AB”的位置，大大提高了效率。

---

部分經(jīng)典KMP例題：

• HDU-2087
• HDU-2203
• HDU-1867
• HDU-3336
• HDU-6153
• HDU-3746
• HDU-4300

---

看到這，你已經(jīng)了解了KMP的原理，恭喜你，你成功的邁出了KMP學(xué)習(xí)的第一步！ 接下來，接連不斷的AC掉10道以上的KMP類型題，你就在真正的掌握了KMP算法了。

---

如果這篇文章對你產(chǎn)生了幫助，就請給博主一個一鍵三連吧！有什么問題也可以在評論區(qū)留言指出。

總結(jié)

以上是生活随笔為你收集整理的详解图示+例题演练——BF算法+KMP算法基本原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。