KMP算法詳解（課堂PPT）

1、1本PPT格式說明：代碼全部以圖片形式給出字符串樣例全部以courier new字體給出注釋全部以華文細黑華文細黑字體給出文字講解以微軟雅黑或verdana字體給出數(shù)學公式中的括號全部為半角括號()文字性解釋說明中的括號全部為中文全角括號（）23abababcdabcdbbacabacaababaca4abababcdabcdbbacabacaababaca5abababcdabcdbbacabacaababaca6abababcdabcdbbacabacaababaca7abababcdabcdbbacabacaababaca8abababcdabcdbbacabacaababaca事實上，

2、我們在之前匹配的過程中已經(jīng)知道了s2=bp1=a，i,j都回溯必然失配。那怎樣降低時間復雜度呢？引入KMP算法，使用這個算法可以將上面O(nm)的復雜度降低為O(n+m)。KMP算法的核心思想是：文本串s的指針i不回溯。那是不是只需要在暴力的基礎上保持失配時i不變就行了呢？你會發(fā)現(xiàn)：還是浪費了很多時間。有沒有一種方法可以在失配時讓j直接跳到一個應該跳到的位置上去呢？9這就來到KMP的大核心next數(shù)組。next數(shù)組表示的意思是當前字符之前的子串中最長相同前綴后綴的長度。說人話：當前字符之前模式串P子串最長相同前綴后綴的長度。手寫個小Demo演示一下：abaabcanext 0 0 0 1 1

3、2 0注：一個字符串的相同前綴后綴是不包括這個字符串本身的，比如字符串”ab”，它就沒有相同前綴后綴，字符串”a”同理。10next的意義：如果當前兩個字符失配，那么模式串P應該移動到哪，換言之，應該用P中的哪個字符來繼續(xù)匹配si。保證文本串S的指針i不回溯。next的求解：不必每次記錄前綴后綴，前面匹配成功的字符，后面可以直接拿來用。為什么求一個相同最長前綴后綴長度就可以解決這個問題：假設在模式串紅色位置失配：a b a a a b a c b c失配了，j要回溯，也就是模式串相對于文本串要右移。右移多少位呢？我們發(fā)現(xiàn)，既然當前位置前面的所有字符都匹配成功，那么它最長相同前綴后綴上的字符也都

4、相同。這些相同前綴后綴上的字符不需要再匹配，用這之中前綴的后面一個字符匹配當前字符即可，即失配時，模式串向右移動的位數(shù)為：已匹配字符數(shù) - 失配字符的上一位字符所對應的最大長度值。11算法一的錯誤之處在于：如果出現(xiàn)沒出現(xiàn)過的字符，會陷入死循環(huán)。abaabcanext 0 0 0 1 1 ?12/i/i為為nextnext的下標，的下標，t t為為nextnext的值的值/-1/-1和和0 0都表示沒有相同的前綴后綴都表示沒有相同的前綴后綴/t=-1/t=-1同樣可以達到同樣可以達到next1=0next1=0的效果，想想為什么的效果，想想為什么/從從1 1到到(lenp-1)(lenp-1)枚

5、舉枚舉i i/賦值賦值nextnext/如果這是一個新字符如果這是一個新字符(t=-1)(t=-1)那么就賦值那么就賦值nextinexti為為0 0（-1+1=0-1+1=0）。）。t=nexttt=nextt的含義其實是的含義其實是t=nextt-1+1t=nextt-1+1。a b a a b c anext -1 0 0 1 1 2 0i13求完了next數(shù)組，下面就可以開始KMP了。模擬之前提到的過程就可以，可以總結為下面兩條規(guī)則：規(guī)則一：如果匹配成功，i+,j+；規(guī)則二：如果失配，i不動，j回溯到nextj。代碼十分容易理解，可能需要解釋的就是輸出模式串所在位置的條件，詳見下頁。14/規(guī)則一規(guī)則一/規(guī)則二規(guī)則二/如果模式串最后一個字符也匹配成功就輸出這個如果模式串最后一個字符也匹配成功就輸出這個/合法位置合法位置如果整