出處：http://blog.csdn.net/v_july_v/article/details/7041827
作者：July時間：最初寫于2011年12月，2014年7月21日晚10點 全部刪除重寫成此文，隨后的半個月從早到晚不斷改進。本KMP原文最初寫于2年多前的2011年12月，因當時初次接觸KMP，思路混亂導致寫也寫得非?；靵y，如此，留言也是“罵聲”一片。所以一直想找機會重新寫下KMP，但苦于一直以來對KMP的理解始終不夠，故才遲遲沒有修改本文。
然近期因在北京開了個算法班，專門講解數據結構、面試、算法，才再次仔細回顧了這個KMP，在綜合了一些網友的理解、以及跟我一起講算法的兩位講師朋友曹博、鄒博的理解之后，寫了9張PPT，發在微博上。隨后，一不做二不休，索性將PPT上的內容整理到了本文之中。
KMP本身不復雜，但網上大部分的文章（包括本文的2011年版本）把它講混亂了。下面，咱們從暴力匹配算法講起，隨后闡述KMP的流程 步驟、next 數組的簡單求解 遞推原理 代碼求解，接著基于next 數組匹配，談到有限狀態自動機，next 數組的優化，KMP的時間復雜度分析，最后簡要給出一個KMP的擴展算法。
全文力圖給你一個最為完整最為清晰的KMP，希望更多的人不再被KMP折磨或糾纏，不再被一些混亂的文章所混亂，有何疑問，歡迎隨時留言評論，thanks。
咱們先來看暴力匹配算法。假設現在文本串S匹配到 i 位置，模式串P匹配到 j 位置
如果當前字符匹配成功（即S[i] == P[j]），則i++，j++，繼續匹配下一個字符； 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0，因為每次匹配失敗時，j 都被置為0，所以i = i+1，相當于失配時模式串P相對于文本串S向右移動一位。理清楚了暴力匹配算法的流程及內在的邏輯，咱們可以寫出暴力匹配的代碼，如下：
int ViolentMatch(char* s, char* p) { int sLen = strlen(s); int pLen = strlen(p); int i = 0; int j = 0; while (i < sLen && j < pLen) { if (s[i] == p[j]) { //①如果當前字符匹配成功（即S[i] == P[j]），則i++，j++ i++; j++; } else { //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0 i = i - j + 1; j = 0; } } //匹配成功，返回模式串p在文本串s中的位置，否則返回-1 if (j == pLen) return i - j; else return -1; } int ViolentMatch(char* s, char* p) { int sLen = strlen(s); int pLen = strlen(p); int i = 0; int j = 0; while (i < sLen && j < pLen) { if (s[i] == p[j]) { //①如果當前字符匹配成功（即S[i] == P[j]），則i++，j++ i++; j++; } else { //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0 i = i - j + 1; j = 0; } } //匹配成功，返回模式串p在文本串s中的位置，否則返回-1 if (j == pLen) return i - j; else return -1; } 舉個例子，如果給定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，現在要拿模式串P去跟文本串S匹配，整個過程如下所示：
1. S[0]為B，P[0]為A，不匹配，執行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相當于模式串要往右移動一位（i=1，j=0）
2. S[1]跟P[0]還是不匹配，繼續執行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），從而模式串不斷的向右移動一位（不斷的執行“令i = i - (j - 1)，j = 0”，i從2變到4，j一直為0）
3. 直到S[4]跟P[0]匹配成功（i=4，j=0），此時按照上面的暴力匹配算法的思路，轉而執行第①條指令：“如果當前字符匹配成功（即S[i] == P[j]），則i++，j++”，可得S[i]為S[5]，P[j]為P[1]，即接下來S[5]跟P[1]匹配（i=5，j=1）
4. S[5]跟P[1]匹配成功，繼續執行第①條指令：“如果當前字符匹配成功（即S[i] == P[j]），則i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此進行下去
5. 直到S[10]為空格字符，P[6]為字符D（i=10，j=6），因為不匹配，重新執行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相當于S[5]跟P[0]匹配（i=5，j=0）
6. 至此，我們可以看到，如果按照暴力匹配算法的思路，盡管之前文本串和模式串已經分別匹配到了S[9]、P[5]，但因為S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，從而讓S[5]跟P[0]匹配。
而S[5]肯定跟P[0]失配。為什么呢？因為在之前第4步匹配中，我們已經得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯過去必然會導致失配。那有沒有一種算法，讓i 不往回退，只需要移動j 即可呢？
答案是肯定的。這種算法就是本文的主旨KMP算法，它利用之前已經部分匹配這個有效信息，保持i 不回溯，通過修改j 的位置，讓模式串盡量地移動到有效的位置。
3. KMP算法
3.1 流程
咱們先給出KMP的結論，以下是KMP的算法流程：
假設現在文本串S匹配到 i 位置，模式串P匹配到 j 位置如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++，繼續匹配下一個字符； 如果j != -1，且當前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串P相對于文本串S向右移動了j - next [j] 位。換言之，當匹配失敗時，模式串向右移動的位數為：失配字符所在位置 - 失配字符對應的next 值，即移動的實際位數為：j - next[j]，且此值大于等于1。 轉換成代碼表示，則是：
int KmpSearch(char* s, char* p) { int i = 0; int j = 0; int sLen = strlen(s); int pLen = strlen(p); while (i < sLen && j < pLen) { //①如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++ if (j == -1 || s[i] == p[j]) { i++; j++; } else { //②如果j != -1，且當前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j] //next[j]即為j所對應的next值 j = next[j]; } } if (j == pLen) return i - j; else return -1; } int KmpSearch(char* s, char* p) { int i = 0; int j = 0; int sLen = strlen(s); int pLen = strlen(p); while (i < sLen && j < pLen) { //①如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++ if (j == -1 || s[i] == p[j]) { i++; j++; } else { //②如果j != -1，且當前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j] //next[j]即為j所對應的next值 j = next[j]; } } if (j == pLen) return i - j; else return -1; } 繼續拿之前的例子來說，當S[10]跟P[6]匹配失敗時，KMP不是簡單的如樸素匹配那樣把模式串右移一位，而是執行第②條指令：“如果j != -1，且當前字符匹配失敗（即S[i] != P[j]），則令 i 不變，j = next[j]”，即j 從6變到2（后面我們將求得P[6]，即字符D對應的next 值為2），所以相當于模式串向右移動的位數為j - next[j]位（j - next[j] = 6-2 = 4位）。
向右移動4位后，S[10]跟P[2]繼續匹配。為什么要向右移動4位呢，因為移動4位后，模式串中又有個“AB”可以繼續跟S[8]S[9]匹配，相當于在模式串中找相同的前綴和后綴，然后根據前綴后綴求出next 數組，最后基于next 數組進行匹配（不關心next 數組怎么求來的，只想看匹配過程是咋樣的，可直接跳到下文3.2.4節）。
3.2 步驟
①尋找前綴后綴最長公共元素長度對于Pj = p0 p1 ...pj-1，尋找模式串Pj中長度最大且相等的前綴和后綴即尋找滿足條件的最大的k，使得p0 p1 ...pk-1 = pj-k pj-k+1...pj-1。也就是說，k是模式串中各個子串的前綴后綴的公共元素的長度，所以求最大的k，就是看某個子串的哪個前綴后綴的公共元素最多。舉個例子，如果給定的模式串為“abaabcaba”，那么它的各個子串的前綴后綴的公共元素的最大長度值如下表格所示：
②求next數組根據第①步驟中求得的各個前綴后綴的公共元素的最大長度求得next 數組，相當于前者右移一位且初值賦為-1，如下表格所示：
③匹配失配，模式串向右移動的位數為：j - next[j]。換言之，當模式串的后綴pj-k pj-k+1...pj-1 跟文本串 si-k si-k+1, ..., si-1失配時，j = next[j]，根據next 數組得到next[j] = k，從而讓模式串的前綴p0 p1 ...pk-1繼續跟文本串 si-k si-k+1, ..., si-1匹配。注：j 是模式串中失配字符的位置，且 j 從0開始計數。 綜上，KMP的next 數組相當于告訴我們：當模式串中的某個字符跟文本串中的某個字符匹配失配時，模式串下一步應該跳到哪個位置。如模式串中在j 處的字符跟文本串在i 處的字符匹配失配時，下一步用next [j] 處的字符繼續跟文本串匹配，相當于模式串向右移動 j - next[j] 位。 接下來，分別具體闡述上述3個步驟。3.2.1 尋找最長前綴后綴
如果給定的模式串是：“ABCDABD”，從左至右遍歷整個模式串，其各個子串的前綴后綴分別如下表格所示：
也就是說，原字符串對應的各個前綴后綴的公共元素的最大長度表為（下簡稱《最大長度表》）：
3.2.2 基于《最大長度表》匹配
因為模式串中首尾可能會有重復的字符，故可得出下述結論：
失配時，模式串向右移動的位數為：已匹配字符數 - 失配字符的上一位字符所對應的最大長度值
下面，咱們就結合之前的《最大長度表》和上述結論，進行字符串的匹配。如果給定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，現在要拿模式串去跟文本串匹配，如下圖所示：
1. 因為模式串中的字符A跟文本串中的字符B、B、C、空格接連不匹配，所以模式串不斷的右移，直到模式串中的字符A跟文本串的第5個字符A匹配成功：
2.繼續往后匹配，當模式串最后一個字符D跟文本串匹配時失配，顯而易見，模式串需要向右移動。但向右移動多少位呢？因為此時已經匹配的字符數為6個（ABCDAB），然后根據《最大長度表》可得失配字符D的上一位字符B對應的長度值為2，所以根據之前的結論，可知需要向右移動6 - 2 = 4 位。
3. 模式串向右移動4位后，發現C處再度失配，因為此時已經匹配了2個字符（AB），且上一個字符B對應的最大長度值為0，所以向右移動：2 - 0 =2 位。 4. A與空格失配，向右移動1 位。
5. 繼續比較，發現D與C 失配，故向右移動的位數為：已匹配的字符數6減去上一位字符B對應的最大長度2，即向右移動6 - 2 = 4 位。 
6. 經歷第5步后，發現匹配成功，過程結束。 
3.2.3 根據《最大長度表》求出next 數組
由上文，我們已經知道，字符串“ABCDABD”各個前綴后綴的最大公共元素長度分別為：
而且，根據這個表可以得出下述結論
失配時，模式串向右移動的位數為：已匹配字符數 - 失配字符的上一位字符所對應的最大長度值 上文利用這個表和結論進行匹配時，我們發現，當匹配到一個字符失配時，其實沒必要考慮當前失配的字符，更何況我們每次失配時，都是看的失配字符的上一位字符對應的最大長度值。如此，便引出了next 數組。
給定字符串“ABCDABD”，可求得它的next 數組如下：
把next 數組跟之前求得的最大長度表對比后，不難發現，next 數組相當于“最大長度值” 整體向右移動一位，然后初始值賦為-1。意識到了這一點，你會驚呼原來next 數組的求解竟然如此簡單：就是找最大對稱長度的前綴后綴，然后整體右移一位，初值賦為-1！
換言之，對于給定的模式串：ABCDABD，它的最大長度表及next 數組分別如下：
根據最大長度表求出了next 數組后，從而有
失配時，模式串向右移動的位數為：失配字符所在位置 - 失配字符對應的next 值
而后，你會發現，無論是基于《最大長度表》的匹配，還是基于next 數組的匹配，兩者得出來的向右移動的位數是一樣的。為什么呢？因為：
根據《最大長度表》，失配時，模式串向右移動的位數 = 已經匹配的字符數 - 失配字符的上一位字符的最大長度值 而根據《next 數組》，失配時，模式串向右移動的位數 = 失配字符的位置 - 失配字符對應的next 值其中，從0開始計數時，失配字符的位置 = 已經匹配的字符數（失配字符不計數），而失配字符對應的next 值 = 失配字符的上一位字符的最大長度值，兩相比較，結果必然完全一致。 接下來，咱們來寫代碼求下next 數組。
基于之前的理解，可知計算next 數組的方法可以采用遞推：
1. 如果對于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相當于next[j] = k。此意味著什么呢？究其本質，next[j] = k 代表p[j] 之前的模式串子串中，有長度為k 的相同前綴和后綴。有了這個next 數組，在KMP匹配中，當模式串后綴中j 處的字符失配時，模式串向右移動j - next[j] 位。舉個例子，如下圖，根據模式串“ABCDABD”的next 數組可知失配位置的字符D對應的next 值為2，代表字符D前有長度為2的相同前綴和后綴（這個相同的前綴后綴即為“AB”），失配后，模式串需要向右移動j - next [j] = 6 - 2 =4位。
向右移動4位后，模式串中的字符C繼續跟文本串匹配。
2. 下面的問題是：已知next [0, ..., j]，如何求出next [j + 1]呢？ 對于pattern的前j+1個序列字符：
若pattern[k] == pattern[j]，則next[j + 1 ] = next [j] + 1 = k + 1； 若pattern[k ] ≠ pattern[j]，如果此時pattern[ next[k] ] == pattern[j ]，則next[ j + 1 ] = next[k] + 1，否則繼續遞歸重復此過程。 相當于在字符p[j+1]之前不存在長度為k+1的前綴"p0 p1, …, pk-1 pk"跟后綴“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一個值t+1 < k+1，使得長度更小的前綴 “p0 p1, …, pt-1 pt” 等于長度更小的后綴 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么這個t+1 便是next[ j+1]的值，此相當于利用next 數組進行P串前綴跟P串后綴的匹配。 一般的文章或教材可能就此一筆帶過，但大部分的初學者可能還是不能很好的理解上述求解next 數組的原理，故接下來，我再來著重說明下。
如下圖所示，假定給定模式串ABCDABCE，且已知next [j] = k（相當于“p0 pk-1” = “pj-k pj-1” = AB，可以看出k為2），現要求next [j + 1]等于多少？因為pk = pj = C，所以next[j + 1] = next[j] + 1 = k + 1（可以看出next[j + 1] = 3）。代表字符E前的模式串中，有長度k+1 的相同前綴后綴。
但如果pk != pj 呢？說明“p0 pk-1 pk” ≠ “pj-k pj-1 pj”。換言之，當pk != pj后，字符E前有多大長度的相同前綴后綴呢？很明顯，因為C不同于D，所以ABC 跟 ABD不相同，即字符E前的模式串沒有長度為k+1的相同前綴后綴，也就不能再簡單的令：next[j + 1] = next[j] + 1 。所以，咱們只能去尋找長度更短一點的相同前綴后綴。
結合上圖來講，若能在前綴“ p0 pk-1 pk ” 中不斷的遞歸k = next [k]，找到一個字符pk’ 也為D，代表pk’ = pj，且滿足p0 pk'-1 pk' = pj-k' pj-1 pj，則最大相同的前綴后綴長度為k' + 1，從而next [j + 1] = k’ + 1 = next [k' ] + 1。否則前綴中沒有D，則代表沒有相同的前綴后綴，next [j + 1] = 0。 所以，因最終在前綴ABC中沒有找到D，故E的next 值為0：模式串的后綴：ABDE模式串的前綴：ABC前綴右移兩位： ABC 此外，咱們還可以換個角度思考這個問題：類似KMP的匹配思路，當p0 p1, ..., pj 跟主串s0 s1, ..., si匹配時，如果模式串在j處失配，則j = next [j]，相當于模式串需要向右移動j - next[j] 位。現在前綴“p0 pk-1 pk” 去跟后綴 “pj-k pj-1 pj”匹配，發現在pk處匹配失敗，那么前綴需要向右移動多少位呢？根據已經求得的前綴各個字符的next 值，可得前綴應該向右移動k - next[k]位，相當于k = next[k]。若移動之后，pk' = pj，則代表字符E前存在長度為next[ k' ] + 1的相同前綴后綴； 否則繼續遞歸k = next [k]，直到pk’’ 跟pj匹配成功，或者不存在任何k（0 < k < j）滿足pk = pj ，且 k = next[k] = -1停止遞歸。 綜上，可以求得next 數組，代碼如下所示：
void GetNext(char* p,int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前綴，p[j]表示后綴 if (k == -1 || p[j] == p[k]) { ++j; ++k; next[j] = k; } else { k = next[k]; } } } void GetNext(char* p,int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前綴，p[j]表示后綴 if (k == -1 || p[j] == p[k]) { ++j; ++k; next[j] = k; } else { k = next[k]; } } } 3.2.4 基于《next 數組》匹配
下面，我們來基于next 數組進行匹配。
還是給定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，現在要拿模式串去跟文本串匹配，如下圖所示：
在正式匹配之前，讓我們來再次回顧下上文2.1節所述的KMP算法的匹配流程：
“假設現在文本串S匹配到 i 位置，模式串P匹配到 j 位置如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++，繼續匹配下一個字符；如果j != -1，且當前字符匹配失敗（即S[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串P相對于文本串S向右移動了j - next [j] 位。換言之，當匹配失敗時，模式串向右移動的位數為：失配字符所在位置 - 失配字符對應的next 值，即移動的實際位數為：j - next[j]，且此值大于等于1。”1. 最開始匹配時P[0]跟S[0]匹配失敗所以執行“如果j != -1，且當前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]”，所以j = -1，故轉而執行“如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++”，得到i = 1，j = 0，即P[0]繼續跟S[1]匹配。P[0]跟S[1]又失配，j再次等于-1，i、j繼續自增，從而P[0]跟S[2]匹配。 P[0]跟S[2]失配后，P[0]又跟S[3]匹配。 P[0]跟S[3]再失配，直到P[0]跟S[4]匹配成功，開始執行此條指令的后半段：“如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++”。2. P[1]跟S[5]匹配成功，P[2]跟S[6]也匹配成功, ...，直到當匹配到字符D時失配（即S[10] != P[6]），由于 j 從0開始計數，故數到失配的字符D時 j 為6，且字符D對應的next 值為2，所以向右移動的位數為：j - next[j] = 6 - 2 =4 位
3. 向右移動4位后，C再次失配，向右移動：j - next[j] = 2 - 0 = 2 位
4. 移動兩位之后，A 跟空格不匹配，再次后移1 位
5. D處失配，向右移動 j - next[j] = 6 - 2 = 4 位6. 匹配成功，過程結束。
匹配過程一模一樣。也從側面佐證了，next 數組確實是只要將各個最大前綴后綴的公共元素的長度值右移一位，且把初值賦為-1 即可。
3.2.5 基于《最大長度表》與基于《next 數組》等價
其實，利用next 數組進行匹配失配時，模式串向右移動 j - next [ j ] 位，等價于已匹配字符數 - 失配字符的上一位字符所對應的最大長度值。為什么呢？
j 從0開始計數，那么當數到失配字符時，j 的數值就是已匹配的字符數； 由于next 數組是由最大長度值表整體向右移動一位（且初值賦為-1）得到的，那么失配字符的上一位字符所對應的最大長度值，即為當前失配字符的next 值。 那為何本文不直接利用next 數組進行匹配呢？因為next 數組不好求，而一個字符串的前綴后綴的公共元素的最大長度值很容易求，例如若給定模式串“ababa”，要你求其next 數組，則乍一看，無從求起。而如果你求其前綴后綴公共元素的最大長度，則很容易得出是：0 0 1 2 3，如下表格所示：
然后這5個數字 全部整體右移一位，且初值賦為-1，即得到其next 數組：-1 0 0 1 2。
3.2.6 Next 數組與有限狀態自動機
next 負責把模式串向前移動，且當第j位不匹配的時候，用第next[j]位和主串匹配，就像打了張“表”。此外，next 也可以看作有限狀態自動機的狀態，在已經讀了多少字符的情況下，失配后，前面讀的若干個字符是有用的。
3.2.7 Next 數組的優化
行文至此，咱們全面了解了暴力匹配的思路、KMP算法的原理、流程、流程之間的內在邏輯聯系，以及next 數組的簡單求解（《最大長度表》整體右移一位，然后初值賦為-1）和代碼求解，最后基于《next 數組》的匹配，看似洋洋灑灑，清晰透徹，但以上忽略了一個小問題。
比如，如果用之前的next 數組方法求模式串“abab”的next 數組，可得其next 數組為-1 0 0 1（0 0 1 2整體右移一位，初值賦為-1），當它跟下圖中的文本串去匹配的時候，發現b跟c失配，于是模式串右移j - next[j] = 3 - 1 =2位。
右移2位后，b又跟c失配。事實上，因為在上一步的匹配中，已經得知p[3] = b，與s[3] = c失配，而右移兩位之后，讓p[ next[3] ] = p[1] = b 再跟s[3]匹配時，必然失配。問題出在哪呢？
問題出在不該出現p[j] = p[ next[j] ]。為什么呢？理由是：
當p[j] != s[i] 時，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然導致后一步匹配失敗，所以不能允許p[j] = p[ next[j ]]。因為p[j]已經跟s[i]失配，然后你還用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很顯然，必然失配。 所以，咱們得修改下求next 數組的代碼。
//優化過后的next 數組求法 void GetNextval(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前綴，p[j]表示后綴 if (k == -1 || p[j] == p[k]) { ++j; ++k; //較之前next數組求法，改動在下面4行 if (p[j] != p[k]) next[j] = k; //之前只有這一行 else //因為不能出現p[j] = p[ next[j ]]，所以當出現時需要繼續遞歸，k = next[k] = next[next[k]] next[j] = next[k]; } else { k = next[k]; } } } //優化過后的next 數組求法 void GetNextval(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前綴，p[j]表示后綴 if (k == -1 || p[j] == p[k]) { ++j; ++k; //較之前next數組求法，改動在下面4行 if (p[j] != p[k]) next[j] = k; //之前只有這一行 else //因為不能出現p[j] = p[ next[j ]]，所以當出現時需要繼續遞歸，k = next[k] = next[next[k]] next[j] = next[k]; } else { k = next[k]; } } } 利用優化過后的next 數組求法，可知模式串“abab”的新next數組為：-1 0 -1 0（讀者可以在腦海里或紙上執行上述代碼驗證下，如不會計算，可看下文末的參考文獻10）。 可能有些讀者會問：原始next 數組是前綴后綴最長公共元素長度值右移一位， 然后初值賦為-1而得，那么優化后的next 數組如何快速心算出呢？實際上，只要求出了原始next 數組，那么可根據原始next 數組快速求出優化后的next 數組。還是以abab為例，如下表格所示：
然后引用下之前3.1節的KMP代碼：
int KmpSearch(char* s, char* p) { int i = 0; int j = 0; int sLen = strlen(s); int pLen = strlen(p); while (i < sLen && j < pLen) { //①如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++ if (j == -1 || s[i] == p[j]) { i++; j++; } else { //②如果j != -1，且當前字符匹配失敗（即S[i] != P[j]），則令 i 不變，j = next[j] //next[j]即為j所對應的next值 j = next[j]; } } if (j == pLen) return i - j; else return -1; } int KmpSearch(char* s, char* p) { int i = 0; int j = 0; int sLen = strlen(s); int pLen = strlen(p); while (i < sLen && j < pLen) { //①如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++ if (j == -1 || s[i] == p[j]) { i++; j++; } else { //②如果j != -1，且當前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j] //next[j]即為j所對應的next值 j = next[j]; } } if (j == pLen) return i - j; else return -1; } 接下來，咱們繼續拿之前的例子說明，整個匹配過程如下： 1. S[3]與P[3]匹配失敗。
2. S[3]保持不變，P的下一個匹配位置是P[next[3]]，而next[3]=0，所以P[next[3]]=P[0]與S[3]匹配。
3. 由于上一步驟中P[0]與S[3]還是不匹配。此時i=3，j=next [0]=-1，由于滿足條件j==-1，所以執行“++i, ++j”，即主串指針下移一個位置，P[0]與S[4]開始匹配。最后j==pLen，跳出循環，輸出結果i - j = 4（即模式串第一次在文本串中出現的位置），匹配成功，算法結束。
3.3 KMP的時間復雜度分析
咱們先來回顧下KMP匹配算法的流程：
“KMP的算法流程：
假設現在文本串S匹配到 i 位置，模式串P匹配到 j 位置如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++，繼續匹配下一個字符； 如果j != -1，且當前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串P相對于文本串S向右移動了j - next [j] 位?！?p> 我們發現如果某個字符匹配成功，模式串首字符的位置保持不動，僅僅是i++、j++；如果匹配失配，i 不變（即 i 不回溯），模式串會跳過匹配過的next [j]個字符。整個算法最壞的情況是，當模式串首字符位于i - j的位置時才匹配成功，算法結束。 所以，如果文本串的長度為n，模式串的長度為m，那么匹配過程的時間復雜度為O(n)，算上計算next的O(m)時間，KMP的整體時間復雜度為O(m + n)。4. 擴展：BM算法
1977年，德克薩斯大學的Robert S. Boyer教授和J Strother Moore教授發明了一種新的字符串匹配算法：Boyer-Moore算法，該算法擁有在最壞情況下O(N)的時間復雜度，并且，在實踐中，比KMP算法的實際效能高。
BM算法定義了兩個規則：
壞字符規則：當文本串中的某個字符跟模式串的某個字符不匹配時，我們稱文本串中的這個失配字符為壞字符，此時模式串需要向右移動，移動的位數 = 壞字符在模式串中的位置 - 壞字符在模式串中最右出現的位置。此外，如果"壞字符"不包含在模式串之中，則最右出現位置為-1。好后綴規則：當字符失配時，后移位數 = 好后綴在模式串中的位置 - 好后綴在模式串上一次出現的位置，且如果好后綴在模式串中沒有再次出現，則為-1。 下面舉例說明BM算法。例如，給定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，現要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。
1. 首先，"文本串"與"模式串"頭部對齊，從尾部開始比較。"S"與"E"不匹配。這時，"S"就被稱為"壞字符"（bad character），即不匹配的字符，它出現在模式串的第6位。且"S"不包含在模式串"EXAMPLE"之中（相當于最右出現位置是-1），這意味著可以把模式串后移6-(-1)=7位，從而直接移到"S"的后一位。
2. 依然從尾部開始比較，發現"P"與"E"不匹配，所以"P"是"壞字符"。但是，"P"包含在模式串"EXAMPLE"之中。因為“P”這個“壞字符”出現在模式串的第6位（從0開始編號），且在模式串中的最右出現位置為4，所以，將模式串后移6-4=2位，兩個"P"對齊。
3. 依次比較，得到 “MPLE”匹配，稱為"好后綴"（good suffix），即所有尾部匹配的字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后綴。
4. 發現“I”與“A”不匹配：“I”是壞字符。如果是根據壞字符規則，此時模式串應該后移2-(-1)=3位。問題是，有沒有更優的移法？
5. 更優的移法是利用好后綴規則：當字符失配時，后移位數 = 好后綴在模式串中的位置 - 好后綴在模式串中上一次出現的位置，且如果好后綴在模式串中沒有再次出現，則為-1。 所有的“好后綴”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的頭部出現，所以后移6-0=6位。 可以看出，“壞字符規則”只能移3位，“好后綴規則”可以移6位。每次后移這兩個規則之中的較大值。這兩個規則的移動位數，只與模式串有關，與原文本串無關。
6. 繼續從尾部開始比較，“P”與“E”不匹配，因此“P”是“壞字符”，根據“壞字符規則”，后移 6 - 4 = 2位。因為是最后一位就失配，尚未獲得好后綴。
由上可知，BM算法不僅效率高，而且構思巧妙，容易理解。完。5. 參考文獻
《算法導論》的第十二章：字符串匹配； 本文中模式串“ABCDABD”的圖來自于此文：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93PRatt_algorithm.html；本文最后一張有限狀態自動機的手繪圖來自于北京算法班周日班講師曹博的PPT； 北京7月暑假班鄒博半小時KMP視頻：http://v.youku.com/v_show/id_XNzQzMjQ1OTYw.html；北京7月暑假班鄒博第二次課的PPT：http://yun.baidu.com/s/1mgFmw7u；理解KMP 的9張PPT：http://weibo.com/1580904460/BeCCYrKz3#_rnd1405957424876；詳解KMP算法（多圖）：http://www.49028c.com/yjiyjige/p/3263858.html；最后一部分的BM算法參考自此文：http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html；http://youlvconglin.blog.163.com/blog/static/5232042010530101020857；《數據結構 第二版》，嚴蔚敏 & 吳偉民編著； 六之續、由KMP算法談到BM算法：http://blog.csdn.net/v_JULY_v/article/details/6545192。6. 后記
對之前混亂的文章給廣大讀者帶來的困擾表示致歉，對重新寫就后的本文即將給讀者帶來的清晰表示欣慰。希望大部分的初學者，甚至少部分的非計算機專業讀者也能看懂此文。有任何問題，歡迎隨時批評指正，thanks。
July、二零一四年八月四日。
新聞熱點
疑難解答
