一文理解KMP算法

作者：July
時間：最初寫于2011年12月，2014年7月21日晚10點全部刪除重寫成此文，隨后的半個多月不斷反復改進。后收錄于新書《編程之法：面試和算法心得》第4.4節中。

1. 引言

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

? ? 然近期因開了個算法班，班上專門講解數據結構、面試、算法，才再次仔細回顧了這個KMP，在綜合了一些網友的理解、以及算法班的兩位講師朋友曹博、鄒博的理解之后，寫了9張PPT，發在微博上。隨后，一不做二不休，索性將PPT上的內容整理到了本文之中（后來文章越寫越完整，所含內容早已不再是九張PPT 那樣簡單了）。

? ? 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。

? ? 理清楚了暴力匹配算法的流程及內在的邏輯，咱們可以寫出暴力匹配的代碼，如下：


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 定義

? ??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 個字符。

? ? 轉換成代碼表示，則是：


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;
}

? ? 繼續拿之前的例子來說，當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。

<ul><li>此意味著什么呢？究其本質，<strong>next[j] = k 代表p[j] 之前的模式串子串中，有長度為k 的相同前綴和后綴</strong>。有了這個next 數組，在KMP匹配中，當模式串中j 處的字符失配時，下一步用next[j]處的字符繼續跟文本串匹配，相當于模式串向右移動j - next[j] 位。</li>
</ul></li>

舉個例子，如下圖，根據模式串“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]，直到要么找到長度更短的相同前綴后綴，要么沒有長度更短的相同前綴后綴。如下圖所示：

? ?

引用下一讀者wudehua55555于本文評論下留言，以輔助大家從另一個角度理解：“?一直以為博主在用遞歸求next數組時沒講清楚，為何要用k = next[k],仔細看了這個紅黃藍分區圖才突然恍然大悟，就是找到p[k]對應的next[k]，根據對稱性，只需再判斷p[next[k]]與p[j]是否相等即可，于是令k = next[k],這里恰好就使用了遞歸的思路。其實我覺得不要一開始就陷入遞歸的方法中，換一種思路，直接從考慮對稱性入手，可直接得出k = next[k]，而這正好是遞歸罷了。以上是一些個人看法，非常感謝博主提供的解析，非計算機的學生也能看懂，雖然從昨晚9點看到了現在。高興。”

? ? 所以，因最終在前綴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 數組，代碼如下所示：


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]) 
{
++k;
++j;
next[j] = k;
}
		else 
{
k = next[k];
}
}
}

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

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

3.3.5 基于《next 數組》匹配

? ? 下面，我們來基于next 數組進行匹配。

?

? ? 還是給定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，現在要拿模式串去跟文本串匹配，如下圖所示：

? ? 在正式匹配之前，讓我們來再次回顧下上文2.1節所述的KMP算法的匹配流程：

“假設現在文本串S匹配到 i 位置，模式串P匹配到 j 位置

<ul><li>如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++，繼續匹配下一個字符；</li><li>如果j != -1，且當前字符匹配失敗（即S[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串P相對于文本串S向右移動了j - next [j] 位。<ul><li>換言之，當匹配失敗時，模式串向右移動的位數為：失配字符所在位置 - 失配字符對應的next 值，即<strong>移動的實際位數為：j - next[j]</strong>，且此值大于等于1。<strong>”</strong></li></ul></li>
</ul></li>

1. 最開始匹配時

<ul><li>P[0]跟S[0]匹配失敗<ul><li>所以執行“如果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]匹配。</li></ul></li><li>P[0]跟S[1]又失配，j再次等于-1，i、j繼續自增，從而P[0]跟S[2]匹配。</li><li>P[0]跟S[2]失配后，P[0]又跟S[3]匹配。</li><li>P[0]跟S[3]再失配，直到P[0]跟S[4]匹配成功，開始執行此條指令的后半段：“如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++”。</li>
</ul></li>

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 ] 位，等價于已匹配字符數?- 失配字符的上一位字符所對應的最大長度值。原因是：

j 從0開始計數，那么當數到失配字符時，j 的數值就是已匹配的字符數；
由于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 數組的代碼。


//優化過后的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。可能有些讀者會問：原始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代碼：


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;
}

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

? ? 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非常容易，無非是循序漸進把握好下面幾點：

如果模式串中存在相同前綴和后綴，即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繼續匹配。
之前本應是pj跟si匹配，結果失配了，失配后，令pk跟si匹配，相當于j 變成了k，模式串向右移動j - k位。
因為k 的值是可變的，所以我們用next[j]表示j處字符失配后，下一次匹配模式串應該跳到的位置。換言之，失配前是j，pj跟si失配時，用p[ next[j] ]繼續跟si匹配，相當于j變成了next[j]，所以，j = next[j]，等價于把模式串向右移動j - next [j] 位。
而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. 參考文獻

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