資源描述：
《KMP算法詳解課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、本PPT格式說(shuō)明：代碼全部以圖片形式給出字符串樣例全部以couriernew字體給出注釋全部以華文細(xì)黑字體給出文字講解以微軟雅黑或verdana字體給出數(shù)學(xué)公式中的括號(hào)全部為半角括號(hào)()文字性解釋說(shuō)明中的括號(hào)全部為中文全角括號(hào)（）KMPKnuth-Morris-Pratt字符串匹配查找算法abababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPa
2、bababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaP事實(shí)上，我們?cè)谥捌ヅ涞倪^(guò)程中已經(jīng)知道了s[2]=b≠p[1]=a，i,j都回溯必然失配。那怎樣降低時(shí)間復(fù)雜度呢？引入KMP算法，使用這個(gè)算法可以將上面O(nm)的復(fù)雜度降低為O(n+m)。KMP算法的核心思想是：文本串s的指針i不回溯。那是不是只需要在暴力的基礎(chǔ)上保持失配時(shí)i不變就行了呢？你會(huì)發(fā)現(xiàn)：還是浪費(fèi)了很多時(shí)間。有沒(méi)有一種方法可以在失配時(shí)讓j直接跳到一個(gè)應(yīng)該跳到的位置上去呢？這就來(lái)到KMP的大核心——n
3、ext數(shù)組。next數(shù)組表示的意思是當(dāng)前字符之前的子串中最長(zhǎng)相同前綴后綴的長(zhǎng)度。說(shuō)人話：當(dāng)前字符之前模式串P子串最長(zhǎng)相同前綴后綴的長(zhǎng)度。手寫個(gè)小Demo演示一下：abaabcaPnext0001120注：一個(gè)字符串的相同前綴后綴是不包括這個(gè)字符串本身的，比如字符串”ab”，它就沒(méi)有相同前綴后綴，字符串”a”同理。next的意義：如果當(dāng)前兩個(gè)字符失配，那么模式串P應(yīng)該移動(dòng)到哪，換言之，應(yīng)該用P中的哪個(gè)字符來(lái)繼續(xù)匹配s[i]。保證文本串S的指針i不回溯。next的求解：不必每次記錄前綴后綴，前面匹配成功的字符，后面可以直接拿來(lái)用。
4、為什么求一個(gè)相同最長(zhǎng)前綴后綴長(zhǎng)度就可以解決這個(gè)問(wèn)題：假設(shè)在模式串紅色位置失配：abaaabacbc失配了，j要回溯，也就是模式串相對(duì)于文本串要右移。右移多少位呢？我們發(fā)現(xiàn)，既然當(dāng)前位置前面的所有字符都匹配成功，那么它最長(zhǎng)相同前綴后綴上的字符也都相同。這些相同前綴后綴上的字符不需要再匹配，用這之中前綴的后面一個(gè)字符匹配當(dāng)前字符即可，即失配時(shí)，模式串向右移動(dòng)的位數(shù)為：已匹配字符數(shù)-失配字符的上一位字符所對(duì)應(yīng)的最大長(zhǎng)度值。算法一的錯(cuò)誤之處在于：如果出現(xiàn)沒(méi)出現(xiàn)過(guò)的字符，會(huì)陷入死循環(huán)。abaabcaPnext00011?//i為next
5、[]的下標(biāo)，t為next[]的值//-1和0都表示沒(méi)有相同的前綴后綴//t=-1同樣可以達(dá)到next[1]=0的效果，想想為什么//從1到(lenp-1)枚舉i//①//賦值next[]//②①如果這是一個(gè)新字符(t==-1)那么就賦值next[i]為0（-1+1=0）。②t=next[t]的含義其實(shí)是t=next[t]-1+1。abaabcaPnext-1001120it求完了next數(shù)組，下面就可以開(kāi)始KMP了。模擬之前提到的過(guò)程就可以，可以總結(jié)為下面兩條規(guī)則：規(guī)則一：如果匹配成功，i++,j++；規(guī)則二：如果失配，i不動(dòng)
6、，j回溯到next[j]。代碼十分容易理解，可能需要解釋的就是輸出模式串所在位置的條件，詳見(jiàn)下頁(yè)。//規(guī)則一//規(guī)則二//如果模式串最后一個(gè)字符也匹配成功就輸出這個(gè)//合法位置如果整個(gè)模式串匹配成功，j要回溯到next[j]。至此，KMP算法介紹結(jié)束。時(shí)間復(fù)雜度O(lens+lenp)。謝謝~
