KMP算法詳解（課堂PPT）

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

2、我們?cè)谥捌ヅ涞倪^(guò)程中已經(jīng)知道了s2=bp1=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)該跳到的位置上去呢？9這就來(lái)到KMP的大核心next數(shù)組。next數(shù)組表示的意思是當(dāng)前字符之前的子串中最長(zhǎng)相同前綴后綴的長(zhǎng)度。說(shuō)人話：當(dāng)前字符之前模式串P子串最長(zhǎng)相同前綴后綴的長(zhǎng)度。手寫(xiě)個(gè)小Demo演示一下：abaabcanext 0 0 0 1 1

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

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

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