法又稱“看毛片”算法，是一個(gè)效率非常高的字符串匹配算法。不過(guò)由于其難以理解，所以在很長(zhǎng)的一段時(shí)間內(nèi)一直沒(méi)有搞懂。雖然網(wǎng)上有很多資料，但是鮮見(jiàn)好的博客能簡(jiǎn)單明了地將其講清楚。在此，綜合網(wǎng)上比較好的幾個(gè)博客（參見(jiàn)最后），盡自己的努力爭(zhēng)取將kmp算法思想和實(shí)現(xiàn)講清楚。
kmp算法完成的任務(wù)是：給定兩個(gè)字符串O和f，長(zhǎng)度分別為n和m，判斷f是否在O中出現(xiàn)，如果出現(xiàn)則返回出現(xiàn)的位置。常規(guī)方法是遍歷a的每一個(gè)位置，然后從該位置開(kāi)始和b進(jìn)行匹配，但是這種方法的復(fù)雜度是O(nm)。kmp算法通過(guò)一個(gè)O(m)的預(yù)處理，使匹配的復(fù)雜度降為O(n+m)。
kmp算法思想
我們首先用一個(gè)圖來(lái)描述kmp算法的思想。在字符串O中尋找f，當(dāng)匹配到位置i時(shí)兩個(gè)字符串不相等，這時(shí)我們需要將字符串f向前移動(dòng)。常規(guī)方法是每次向前移動(dòng)一位，但是它沒(méi)有考慮前i-1位已經(jīng)比較過(guò)這個(gè)事實(shí)，所以效率不高。事實(shí)上，如果我們提前計(jì)算某些信息，就有可能一次前移多位。假設(shè)我們根據(jù)已經(jīng)獲得的信息知道可以前移k位，我們分析移位前后的f有什么特點(diǎn)。我們可以得到如下的結(jié)論：
A段字符串是f的一個(gè)前綴。
B段字符串是f的一個(gè)后綴。
A段字符串和B段字符串相等。
所以前移k位之后，可以繼續(xù)比較位置i的前提是f的前i-1個(gè)位置滿足：長(zhǎng)度為i-k-1的前綴A和后綴B相同。只有這樣，我們才可以前移k位后從新的位置繼續(xù)比較。
延伸閱讀
學(xué)習(xí)是年輕人改變自己的最好方式