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