KMP算法詳解課件學習資料.ppt

《KMP算法詳解課件學習資料.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、KMP算法詳解課件abababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaP事實上，我們在之前匹配的過程中已經知道了s[2]=b≠p[1]=a，i,j都回溯必然失配。那怎樣降低時間復雜度呢？引入KMP算法，使用這個算法可以將上面O(nm)的復雜度降低為O(n+m)。KM

2、P算法的核心思想是：文本串s的指針i不回溯。那是不是只需要在暴力的基礎上保持失配時i不變就行了呢？你會發(fā)現(xiàn)：還是浪費了很多時間。有沒有一種方法可以在失配時讓j直接跳到一個應該跳到的位置上去呢？這就來到KMP的大核心——next數(shù)組。next數(shù)組表示的意思是當前字符之前的子串中最長相同前綴后綴的長度。說人話：當前字符之前模式串P子串最長相同前綴后綴的長度。手寫個小Demo演示一下：abaabcaPnext0001120注：一個字符串的相同前綴后綴是不包括這個字符串本身的，比如字符串”ab”，它就沒有相同前綴后綴，字符串”a”同理。next的意義：如果當前兩個字符失配，

3、那么模式串P應該移動到哪，換言之，應該用P中的哪個字符來繼續(xù)匹配s[i]。保證文本串S的指針i不回溯。next的求解：不必每次記錄前綴后綴，前面匹配成功的字符，后面可以直接拿來用。為什么求一個相同最長前綴后綴長度就可以解決這個問題：假設在模式串紅色位置失配：abaaabacbc失配了，j要回溯，也就是模式串相對于文本串要右移。右移多少位呢？我們發(fā)現(xiàn)，既然當前位置前面的所有字符都匹配成功，那么它最長相同前綴后綴上的字符也都相同。這些相同前綴后綴上的字符不需要再匹配，用這之中前綴的后面一個字符匹配當前字符即可，即失配時，模式串向右移動的位數(shù)為：已匹配字符數(shù)-失配字符的上

4、一位字符所對應的最大長度值。算法一的錯誤之處在于：如果出現(xiàn)沒出現(xiàn)過的字符，會陷入死循環(huán)。abaabcaPnext00011?//i為next[]的下標，t為next[]的值//-1和0都表示沒有相同的前綴后綴//t=-1同樣可以達到next[1]=0的效果，想想為什么//從1到(lenp-1)枚舉i//①//賦值next[]//②①如果這是一個新字符(t==-1)那么就賦值next[i]為0（-1+1=0）。②t=next[t]的含義其實是t=next[t]-1+1。abaabcaPnext-1001120it求完了next數(shù)組，下面就可以開始KMP了。模擬之前提到

5、的過程就可以，可以總結為下面兩條規(guī)則：規(guī)則一：如果匹配成功，i++,j++；規(guī)則二：如果失配，i不動，j回溯到next[j]。代碼十分容易理解，可能需要解釋的就是輸出模式串所在位置的條件，詳見下頁。//規(guī)則一//規(guī)則二//如果模式串最后一個字符也匹配成功就輸出這個//合法位置如果整個模式串匹配成功，j要回溯到next[j]。至此，KMP算法介紹結束。時間復雜度O(lens+lenp)。謝謝~此課件下載可自行編輯修改，僅供參考！感謝您的支持，我們努力做得更好！謝謝