很詳盡KMP算法（厲害）

ZzUuOo666

我還是一個在校小猿，為了深入的學習知識，讓知識印象更深刻，決定學寫部落格。

作者：July

時間：最初寫于2011年12月，2014年7月21日晚10點 全部删除重寫成此文，随後的半個多月不斷反複改進。後收錄于新書《程式設計之法：面試和算法心得》第4.4節中。

1. 引言

    本KMP原文最初寫于2年多前的2011年12月，因當時初次接觸KMP，思路混亂導緻寫也寫得混亂。是以一直想找機會重新寫下KMP，但苦于一直以來對KMP的了解始終不夠，故才遲遲沒有修改本文。

    KMP本身不複雜，但網上絕大部分的文章（包括本文的2011年版本）把它講混亂了。下面，咱們從暴力比對算法講起，随後闡述KMP的流程 步驟、next 數組的簡單求解 遞推原理 代碼求解，接着基于next 數組比對，談到有限狀态自動機，next 數組的優化，KMP的時間複雜度分析，最後簡要介紹兩個KMP的擴充算法。

    全文力圖給你一個最為完整最為清晰的KMP，希望更多的人不再被KMP折磨或糾纏，不再被一些混亂的文章所混亂。有何疑問，歡迎随時留言評論，thanks。

2. 暴力比對算法

    假設現在我們面臨這樣一個問題：有一個文本串S，和一個模式串P，現在要查找P在S中的位置，怎麼查找呢？

    如果用暴力比對的思路，并假設現在文本串S比對到 i 位置，模式串P比對到 j 位置，則有：

• 如果目前字元比對成功（即S[i] == P[j]），則i++，j++，繼續比對下一個字元；
• 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相當于每次比對失敗時，i 回溯，j 被置為0。

    理清楚了暴力比對算法的流程及内在的邏輯，咱們可以寫出暴力比對的代碼，如下：

1. int ViolentMatch(char* s, char* p)  
2. {  
3.     int sLen = strlen(s);  
4.     int pLen = strlen(p);  
5.     int i = 0;  
6.     int j = 0;  
7.     while (i < sLen && j < pLen)  
8.     {  
9.         if (s[i] == p[j])  
10.         {  
11.             //①如果目前字元比對成功（即S[i] == P[j]），則i++，j++      
12.             i++;  
13.             j++;  
14.         }  
15.         else  
16.         {  
17.             //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0      
18.             i = i - j + 1;  
19.             j = 0;  
20.         }  
21.     }  
22.     //比對成功，傳回模式串p在文本串s中的位置，否則傳回-1  
23.     if (j == pLen)  
24.         return i - j;  
25.     else  
26.         return -1;  
27. }  

    舉個例子，如果給定文本串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 定義

    Knuth-Morris-Pratt 字元串查找算法，簡稱為 “KMP算法”，常用于在一個文本串S内查找一個模式串P 的出現位置，這個算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年聯合發表，故取這3人的姓氏命名此算法。

    下面先直接給出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 值（next 數組的求解會在下文的3.3.3節中詳細闡述），即移動的實際位數為：j - next[j]，且此值大于等于1。

    很快，你也會意識到next 數組各值的含義：代表目前字元之前的字元串中，有多大長度的相同字首字尾。例如如果next [j] = k，代表j 之前的字元串中有最大長度為k 的相同字首字尾。

    此也意味着在某個字元失配時，該字元對應的next 值會告訴你下一步比對中，模式串應該跳到哪個位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，則跳到模式串的開頭字元，若next [j] = k 且 k > 0，代表下次比對跳到j 之前的某個字元，而不是跳到開頭，且具體跳過了k 個字元。

    轉換成代碼表示，則是：

1. int KmpSearch(char* s, char* p)  
2. {  
3.     int i = 0;  
4.     int j = 0;  
5.     int sLen = strlen(s);  
6.     int pLen = strlen(p);  
7.     while (i < sLen && j < pLen)  
8.     {  
9.         //①如果j = -1，或者目前字元比對成功（即S[i] == P[j]），都令i++，j++      
10.         if (j == -1 || s[i] == p[j])  
11.         {  
12.             i++;  
13.             j++;  
14.         }  
15.         else  
16.         {  
17.             //②如果j != -1，且目前字元比對失敗（即S[i] != P[j]），則令 i 不變，j = next[j]      
18.             //next[j]即為j所對應的next值        
19.             j = next[j];  
20.         }  
21.     }  
22.     if (j == pLen)  
23.         return i - j;  
24.     else  
25.         return -1;  
26. }  

    繼續拿之前的例子來說，當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]對應着，進而不用讓i 回溯。相當于在除去字元D的模式串子串中尋找相同的字首和字尾，然後根據字首字尾求出next 數組，最後基于next 數組進行比對（不關心next 數組是怎麼求來的，隻想看比對過程是咋樣的，可直接跳到下文3.3.4節）。

3.2 步驟

• ①尋找字首字尾最長公共元素長度
  • 對于P = p0 p1 ...pj-1 pj，尋找模式串P中長度最大且相等的字首和字尾。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那麼在包含pj的模式串中有最大長度為k+1的相同字首字尾。舉個例子，如果給定的模式串為“abab”，那麼它的各個子串的字首字尾的公共元素的最大長度如下表格所示：

比如對于字元串aba來說，它有長度為1的相同字首字尾a；而對于字元串abab來說，它有長度為2的相同字首字尾ab（相同字首字尾的長度為k + 1，k + 1 = 2）。

• ②求next數組
  • next 數組考慮的是除目前字元外的最長相同字首字尾，是以通過第①步驟求得各個字首字尾的公共元素的最大長度後，隻要稍作變形即可：将第①步驟中求得的值整體右移一位，然後初值賦為-1，如下表格所示：

比如對于aba來說，第3個字元a之前的字元串ab中有長度為0的相同字首字尾，是以第3個字元a對應的next值為0；而對于abab來說，第4個字元b之前的字元串aba中有長度為1的相同字首字尾a，是以第4個字元b對應的next值為1（相同字首字尾的長度為k，k = 1）。

• ③根據next數組進行比對
  • 比對失配，j = next [j]，模式串向右移動的位數為：j - next[j]。換言之，當模式串的字尾pj-k pj-k+1, ..., pj-1 跟文本串si-k si-k+1, ..., si-1比對成功，但pj 跟si比對失敗時，因為next[j] = k，相當于在不包含pj的模式串中有最大長度為k 的相同字首字尾，即p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令j = next[j]，進而讓模式串右移j - next[j] 位，使得模式串的字首p0 p1, ..., pk-1對應着文本串 si-k si-k+1, ..., si-1，而後讓pk 跟si 繼續比對。如下圖所示：

    綜上，KMP的next 數組相當于告訴我們：當模式串中的某個字元跟文本串中的某個字元比對失配時，模式串下一步應該跳到哪個位置。如模式串中在j 處的字元跟文本串在i 處的字元比對失配時，下一步用next [j] 處的字元繼續跟文本串i 處的字元比對，相當于模式串向右移動 j - next[j] 位。

    接下來，分别具體解釋上述3個步驟。

3.3 解釋

3.3.1 尋找最長字首字尾

    如果給定的模式串是：“ABCDABD”，從左至右周遊整個模式串，其各個子串的字首字尾分别如下表格所示：

    也就是說，原模式串子串對應的各個字首字尾的公共元素的最大長度表為（下簡稱《最大長度表》）：

3.3.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步後，發現比對成功，過程結束。

    通過上述比對過程可以看出，問題的關鍵就是尋找模式串中最大長度的相同字首和字尾，找到了模式串中每個字元之前的字首和字尾公共部分的最大長度後，便可基于此比對。而這個最大長度便正是next 數組要表達的含義。

3.3.3 根據《最大長度表》求next 數組

    由上文，我們已經知道，字元串“ABCDABD”各個字首字尾的最大公共元素長度分别為：

    而且，根據這個表可以得出下述結論

• 失配時，模式串向右移動的位數為：已比對字元數 - 失配字元的上一位字元所對應的最大長度值

    上文利用這個表和結論進行比對時，我們發現，當比對到一個字元失配時，其實沒必要考慮目前失配的字元，更何況我們每次失配時，都是看的失配字元的上一位字元對應的最大長度值。如此，便引出了next 數組。

    給定字元串“ABCDABD”，可求得它的next 數組如下：

    把next 數組跟之前求得的最大長度表對比後，不難發現，next 數組相當于“最大長度值” 整體向右移動一位，然後初始值賦為-1。意識到了這一點，你會驚呼原來next 數組的求解竟然如此簡單：就是找最大對稱長度的字首字尾，然後整體右移一位，初值賦為-1（當然，你也可以直接計算某個字元對應的next值，就是看這個字元之前的字元串中有多大長度的相同字首字尾）。

    換言之，對于給定的模式串：ABCDABD，它的最大長度表及next 數組分别如下：

    根據最大長度表求出了next 數組後，進而有

失配時，模式串向右移動的位數為：失配字元所在位置 - 失配字元對應的next 值

    而後，你會發現，無論是基于《最大長度表》的比對，還是基于next 數組的比對，兩者得出來的向右移動的位數是一樣的。為什麼呢？因為：

• 根據《最大長度表》，失配時，模式串向右移動的位數 = 已經比對的字元數 - 失配字元的上一位字元的最大長度值
• 而根據《next 數組》，失配時，模式串向右移動的位數 = 失配字元的位置 - 失配字元對應的next 值
  • 其中，從0開始計數時，失配字元的位置 = 已經比對的字元數（失配字元不計數），而失配字元對應的next 值 = 失配字元的上一位字元的最大長度值，兩相比較，結果必然完全一緻。

    是以，你可以把《最大長度表》看做是next 數組的雛形，甚至就把它當做next 數組也是可以的，差別不過是怎麼用的問題。

3.3.4 通過代碼遞推計算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 處的字元失配時，下一步用next[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]呢？

    對于P的前j+1個序列字元：

• 若p[k] == p[j]，則next[j + 1 ] = next [j] + 1 = k + 1；
• 若p[k ] ≠ p[j]，如果此時p[ next[k] ] == p[j ]，則next[ j + 1 ] =  next[k] + 1，否則繼續遞歸字首索引k = next[k]，而後重複此過程。 相當于在字元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 數組（next [0, ..., k, ..., j]）進行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。

    那為何遞歸字首索引k = next[k]，就能找到長度更短的相同字首字尾呢？這又歸根到next數組的含義。我們拿字首 p0 pk-1 pk 去跟字尾pj-k pj-1 pj比對，如果pk 跟pj 失配，下一步就是用p[next[k]] 去跟pj 繼續比對，如果p[ next[k] ]跟pj還是不比對，則需要尋找長度更短的相同字首字尾，即下一步用p[ next[ next[k] ] ]去跟pj比對。此過程相當于模式串的自我比對，是以不斷的遞歸k = next[k]，直到要麼找到長度更短的相同字首字尾，要麼沒有長度更短的相同字首字尾。如下圖所示：

    是以，因最終在字首ABC中沒有找到D，故E的next 值為0：

模式串的字尾：ABDE

模式串的字首：ABC

字首右移兩位：     ABC

    讀到此，有的讀者可能又有疑問了，那能否舉一個能在字首中找到字元D的例子呢？OK，咱們便來看一個能在字首中找到字元D的例子，如下圖所示：

    給定模式串DABCDABDE，我們很順利的求得字元D之前的“DABCDAB”的各個子串的最長相同字首字尾的長度分别為0 0 0 0 1 2 3，但當周遊到字元D，要求包括D在内的“DABCDABD”最長相同字首字尾時，我們發現pj處的字元D跟pk處的字元C不一樣，換言之，字首DABC的最後一個字元C 跟字尾DABD的最後一個字元D不相同，是以不存在長度為4的相同字首字尾。

    怎麼辦呢？既然沒有長度為4的相同字首字尾，咱們可以尋找長度短點的相同字首字尾，最終，因在p0處發現也有個字元D，p0 = pj，是以p[j]對應的長度值為1，相當于E對應的next 值為1（即字元E之前的字元串“DABCDABD”中有長度為1的相同字首和字尾）。

    綜上，可以通過遞推求得next 數組，代碼如下所示：

1. void GetNext(char* p,int next[])  
2. {  
3.     int pLen = strlen(p);  
4.     next[0] = -1;  
5.     int k = -1;  
6.     int j = 0;  
7.     while (j < pLen - 1)  
8.     {  
9.         //p[k]表示字首，p[j]表示字尾  
10.         if (k == -1 || p[j] == p[k])   
11.         {  
12.             ++k;  
13.             ++j;  
14.             next[j] = k;  
15.         }  
16.         else   
17.         {  
18.             k = next[k];  
19.         }  
20.     }  
21. }  

    用代碼重新計算下“ABCDABD”的next 數組，以驗證之前通過“最長相同字首字尾長度值右移一位，然後初值賦為-1”得到的next 數組是否正确，計算結果如下表格所示：

    從上述表格可以看出，無論是之前通過“最長相同字首字尾長度值右移一位，然後初值賦為-1”得到的next 數組，還是之後通過代碼遞推計算求得的next 數組，結果是完全一緻的。

3.3.5 基于《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，且目前字元比對失敗（即S[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]也比對成功, ...，直到當比對到P[6]處的字元D時失配（即S[10] != P[6]），由于P[6]處的D對應的next 值為2，是以下一步用P[2]處的字元C繼續跟S[10]比對，相當于向右移動：j - next[j] = 6 - 2 =4 位。

• 3. 向右移動4位後，P[2]處的C再次失配，由于C對應的next值為0，是以下一步用P[0]處的字元繼續跟S[10]比對，相當于向右移動：j - next[j] = 2 - 0 = 2 位。

• 4. 移動兩位之後，A 跟空格不比對，模式串後移1 位。

• 5. P[6]處的D再次失配，因為P[6]對應的next值為2，故下一步用P[2]繼續跟文本串比對，相當于模式串向右移動 j - next[j] = 6 - 2 = 4 位。

• 6. 比對成功，過程結束。

    比對過程一模一樣。也從側面佐證了，next 數組确實是隻要将各個最大字首字尾的公共元素的長度值右移一位，且把初值賦為-1 即可。

3.3.6 基于《最大長度表》與基于《next 數組》等價

    我們已經知道，利用next 數組進行比對失配時，模式串向右移動 j - next [ j ] 位，等價于已比對字元數 - 失配字元的上一位字元所對應的最大長度值。原因是：

1. j 從0開始計數，那麼當數到失配字元時，j 的數值就是已比對的字元數；
2. 由于next 數組是由最大長度值表整體向右移動一位（且初值賦為-1）得到的，那麼失配字元的上一位字元所對應的最大長度值，即為目前失配字元的next 值。

    但為何本文不直接利用next 數組進行比對呢？因為next 數組不好求，而一個字元串的字首字尾的公共元素的最大長度值很容易求。例如若給定模式串“ababa”，要你快速口算出其next 數組，乍一看，每次求對應字元的next值時，還得把該字元排除之外，然後看該字元之前的字元串中有最大長度為多大的相同字首字尾，此過程不夠直接。而如果讓你求其字首字尾公共元素的最大長度，則很容易直接得出結果：0 0 1 2 3，如下表格所示：

    然後這5個數字 全部整體右移一位，且初值賦為-1，即得到其next 數組：-1 0 0 1 2。

3.3.7 Next 數組與有限狀态自動機

    next 負責把模式串向前移動，且當第j位不比對的時候，用第next[j]位和主串比對，就像打了張“表”。此外，next 也可以看作有限狀态自動機的狀态，在已經讀了多少字元的情況下，失配後，前面讀的若幹個字元是有用的。

3.3.8 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]已經跟s[i]失配，然後你還用跟p[j]等同的值p[next[j]]去跟s[i]比對，很顯然，必然失配），是以不能允許p[j] = p[ next[j ]]。如果出現了p[j] = p[ next[j] ]咋辦呢？如果出現了，則需要再次遞歸，即令next[j] = next[ next[j] ]。

    是以，咱們得修改下求next 數組的代碼。

1. //優化過後的next 數組求法  
2. void GetNextval(char* p, int next[])  
3. {  
4.     int pLen = strlen(p);  
5.     next[0] = -1;  
6.     int k = -1;  
7.     int j = 0;  
8.     while (j < pLen - 1)  
9.     {  
10.         //p[k]表示字首，p[j]表示字尾    
11.         if (k == -1 || p[j] == p[k])  
12.         {  
13.             ++j;  
14.             ++k;  
15.             //較之前next數組求法，改動在下面4行  
16.             if (p[j] != p[k])  
17.                 next[j] = k;   //之前隻有這一行  
18.             else  
19.                 //因為不能出現p[j] = p[ next[j ]]，是以當出現時需要繼續遞歸，k = next[k] = next[next[k]]  
20.                 next[j] = next[k];  
21.         }  
22.         else  
23.         {  
24.             k = next[k];  
25.         }  
26.     }  
27. }  

    利用優化過後的next 數組求法，可知模式串“abab”的新next數組為：-1 0 -1 0。可能有些讀者會問：原始next 數組是字首字尾最長公共元素長度值右移一位， 然後初值賦為-1而得，那麼優化後的next 數組如何快速心算出呢？實際上，隻要求出了原始next 數組，便可以根據原始next 數組快速求出優化後的next 數組。還是以abab為例，如下表格所示：

隻要出現了p[next[j]] = p[j]的情況，則把next[j]的值再次遞歸。例如在求模式串“abab”的第2個a的next值時，如果是未優化的next值的話，第2個a對應的next值為0，相當于第2個a失配時，下一步比對模式串會用p[0]處的a再次跟文本串比對，必然失配。是以求第2個a的next值時，需要再次遞歸：next[2] = next[ next[2] ] = next[0] = -1（此後，根據優化後的新next值可知，第2個a失配時，執行“如果j = -1，或者目前字元比對成功（即S[i] == P[j]），都令i++，j++，繼續比對下一個字元”），同理，第2個b對應的next值為0。

對于優化後的next數組可以發現一點：如果模式串的字尾跟字首相同，那麼它們的next值也是相同的，例如模式串abcabc，它的字首字尾都是abc，其優化後的next數組為：-1 0 0 -1 0 0，字首字尾abc的next值都為-1 0 0。

    然後引用下之前3.1節的KMP代碼：

1. int KmpSearch(char* s, char* p)  
2. {  
3.     int i = 0;  
4.     int j = 0;  
5.     int sLen = strlen(s);  
6.     int pLen = strlen(p);  
7.     while (i < sLen && j < pLen)  
8.     {  
9.         //①如果j = -1，或者目前字元比對成功（即S[i] == P[j]），都令i++，j++      
10.         if (j == -1 || s[i] == p[j])  
11.         {  
12.             i++;  
13.             j++;  
14.         }  
15.         else  
16.         {  
17.             //②如果j != -1，且目前字元比對失敗（即S[i] != P[j]），則令 i 不變，j = next[j]      
18.             //next[j]即為j所對應的next值        
19.             j = next[j];  
20.         }  
21.     }  
22.     if (j == pLen)  
23.         return i - j;  
24.     else  
25.         return -1;  
26. }  

    接下來，咱們繼續拿之前的例子說明，整個比對過程如下：

    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.4 KMP的時間複雜度分析

    相信大部分讀者讀完上文之後，已經發覺其實了解KMP非常容易，無非是循序漸進把握好下面幾點：

1. 如果模式串中存在相同字首和字尾，即pj-k pj-k+1, ..., pj-1 = p0 p1, ..., pk-1，那麼在pj跟si失配後，讓模式串的字首p0 p1...pk-1對應着文本串si-k si-k+1...si-1，而後讓pk跟si繼續比對。
2. 之前本應是pj跟si比對，結果失配了，失配後，令pk跟si比對，相當于j 變成了k，模式串向右移動j - k位。
3. 因為k 的值是可變的，是以我們用next[j]表示j處字元失配後，下一次比對模式串應該跳到的位置。換言之，失配前是j，pj跟si失配時，用p[ next[j] ]繼續跟si比對，相當于j變成了next[j]，是以，j = next[j]，等價于把模式串向右移動j - next [j] 位。
4. 而next[j]應該等于多少呢？next[j]的值由j 之前的模式串子串中有多大長度的相同字首字尾所決定，如果j 之前的模式串子串中（不含j）有最大長度為k的相同字首字尾，那麼next [j] = k。

    如之前的圖所示：

    接下來，咱們來分析下KMP的時間複雜度。分析之前，先來回顧下KMP比對算法的流程：

“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] 位。”

    我們發現如果某個字元比對成功，模式串首字元的位置保持不動，僅僅是i++、j++；如果比對失配，i 不變（即 i 不回溯），模式串會跳過比對過的next [j]個字元。整個算法最壞的情況是，當模式串首字元位于i - j的位置時才比對成功，算法結束。

    是以，如果文本串的長度為n，模式串的長度為m，那麼比對過程的時間複雜度為O(n)，算上計算next的O(m)時間，KMP的整體時間複雜度為O(m + n)。

4. 擴充1：BM算法

    KMP的比對是從模式串的開頭開始比對的，而1977年，德克薩斯大學的Robert S. Boyer教授和J Strother Moore教授發明了一種新的字元串比對算法：Boyer-Moore算法，簡稱BM算法。該算法從模式串的尾部開始比對，且擁有在最壞情況下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. 擴充2：Sunday算法

    上文中，我們已經介紹了KMP算法和BM算法，這兩個算法在最壞情況下均具有線性的查找時間。但實際上，KMP算法并不比最簡單的c庫函數strstr()快多少，而BM算法雖然通常比KMP算法快，但BM算法也還不是現有字元串查找算法中最快的算法，本文最後再介紹一種比BM算法更快的查找算法即Sunday算法。

    Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：

• 隻不過Sunday算法是從前往後比對，在比對失敗時關注的是文本串中參加比對的最末位字元的下一位字元。
  • 如果該字元沒有在模式串中出現則直接跳過，即移動位數 = 比對串長度 + 1；
  • 否則，其移動位數 = 模式串中最右端的該字元到末尾的距離+1。

    下面舉個例子說明下Sunday算法。假定現在要在文本串"substring searching algorithm"中查找模式串"search"。

    1. 剛開始時，把模式串與文本串左邊對齊：

substring searching algorithm

search

^

    2. 結果發現在第2個字元處發現不比對，不比對時關注文本串中參加比對的最末位字元的下一位字元，即标粗的字元 i，因為模式串search中并不存在i，是以模式串直接跳過一大片，向右移動位數 = 比對串長度 + 1 = 6 + 1 = 7，從 i 之後的那個字元（即字元n）開始下一步的比對，如下圖：

substring searching algorithm

　　　 search

　　　　^

    3. 結果第一個字元就不比對，再看文本串中參加比對的最末位字元的下一位字元，是'r'，它出現在模式串中的倒數第3位，于是把模式串向右移動3位（r 到模式串末尾的距離 + 1 = 2 + 1 =3），使兩個'r'對齊，如下：

substring searching algorithm

　　　　  search

　　　　　　　^

    4. 比對成功。

    回顧整個過程，我們隻移動了兩次模式串就找到了比對位置，緣于Sunday算法每一步的移動量都比較大，效率很高。完。

6. 參考文獻

1. 《算法導論》的第十二章：字元串比對；
2. 本文中模式串“ABCDABD”的部分圖來自于此文：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html；
3. 本文3.3.7節中有限狀态自動機的圖由微網誌網友@龔陸安 繪制：http://d.pr/i/NEiz；
4. 北京7月暑假班鄒博半小時KMP視訊：http://www.julyedu.com/video/play/id/5；
5. 北京7月暑假班鄒博第二次課的PPT：http://yun.baidu.com/s/1mgFmw7u；
6. 了解KMP 的9張PPT：http://weibo.com/1580904460/BeCCYrKz3#_rnd1405957424876；
7. 詳解KMP算法（多圖）：http://www.cnblogs.com/yjiyjige/p/3263858.html；
8. 本文第4部分的BM算法參考自此文：http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html；
9. http://youlvconglin.blog.163.com/blog/static/5232042010530101020857；
10. 《資料結構 第二版》，嚴蔚敏 & 吳偉民編著；
11. http://blog.csdn.net/v_JULY_v/article/details/6545192；
12. http://blog.csdn.net/v_JULY_v/article/details/6111565；
13. Sunday算法的原理與實作：http://blog.chinaunix.net/uid-22237530-id-1781825.html；
14. 模式比對之Sunday算法：http://blog.csdn.net/sunnianzhong/article/details/8820123；
15. 一篇KMP的英文介紹：http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm；
16. 我2014年9月3日在西安電子科技大學的面試&算法講座視訊（第36分鐘~第94分鐘講KMP）：http://www.julyedu.com/video/play/21。
17. 一幅圖了解KMP next數組的求法：http://v.atob.site/kmp-next.html 。

7. 後記    

    對之前混亂的文章給廣大讀者帶來的困擾表示緻歉，對重新寫就後的本文即将給讀者帶來的清晰表示欣慰。希望大部分的初學者，甚至少部分的非計算機專業讀者也能看懂此文。有任何問題，歡迎随時批評指正，thanks。

    July、二零一四年八月二十二日晚九點。