一????RevisionsHistory 1

一???????Revisions History

二???????前言

三???????關于算法學習

四???????KMP算法始末

KMP算法是用來干什么的

KMP算法是怎樣產生的從暴力搜索算法講起

KMP算法的思想

KMP算法的代碼實現

KMP算法改進

使用KMP算法在目標字符串中查找所有匹配的位置

使用Z-BOX算法計算next數組

五???????總結??

本文所述KMP算法源碼可在這里下載：

http://download.csdn.net/detail/sun2043430/5259164

一、???????Revisions History

?

Name	Date	Reason for change	Revision
超然	2013.03.19	First version	1.0
超然	2013.04.15	Added z box algorithm to compute next array	1.0.1
?	?	?	?

?

二、???????前言

免責申明：

本kmp算法介紹及深入分析、邏輯證明、代碼過程優化文章，為了全面演示本人愚鈍的大腦思考過程，寫的又臭又長。讀者在閱讀過程中必然會耗費大量的腦細胞，影響愉快的心情，所以閱讀之前請三思而行，對于閱讀本文造成的任何嚴重及不嚴重的后果本人概不負責：）

三、???????關于算法學習

劉未鵬在他的《知其所以然》系列文章中提到了算法的學習，提出了很多具有代表性的問題，比較典型的有：學習算法為什么這么難？該怎樣去學習算法？

算法的學習為什么這么難？

1 算法本身就是一個比較難的課門。

2 講授算法的書、老師沒有從大家更容易理解的角度去講解。

該怎樣去學習算法？

1 如果說要學習的算法是未知的東西，那么我們必然要從已知處出發，一步一個臺階，層層推進，嚴格推導出該算法。可惜的是，很多老師，很多書籍、文章做不到這一點。

2 在每一步的推導過程中，我們要證明這一步是正確的，這一步是最優的。其他假設的分支都是不正確、不合適的。

3 一個算法的推導過程就像一顆樹一樣，根節點是已知條件，其中的一個葉子節點是我們需要的算法。在推導過程中，我們不僅要演示能夠得到證明的這條路徑，我們還應該盡最大可能地說明其他分支是不正確的分支，或者不是最優分支。

我們應該由淺入深地思考以下問題：

某算法是用來干什么的？

某算法是怎樣產生的？

某算法的本質是什么？

如何嚴格證明（一步一步推導）該算法的正確性？

該算法是不是最優的？是否存在更好的算法？

最后才是：

寫代碼實現該算法！！！

四、???????KMP算法始末

1.?????? KMP算法是用來干什么的？

該算法是用來在目標字符串中查找模式串的。

?

2.?????? KMP算法是怎樣產生的？——從暴力搜索算法講起

說到查找字符串，我們首先想到的就是暴力搜索算法，從目標字符串的第1位開始進行比較，如果目標串的每一個字符都和模式串匹配，那么我們就找到了一個匹配的位置。如果在這一次比較的過程中發現某一位不匹配，那么我們就從目標字符串的第2為開始進行比較……依次進行下去，直到找到匹配的目標字符串的位置或者目標字符串到達了末尾。

寫代碼如下：

void ForceSearch(char *pMain,char* pPattern) {int i = 0;int j = 0;int k = 0;for ( ; '\0' != pMain[k];i++, j = 0,k = i){while (pMain[k] !='\0' && pPattern[j] != '\0' &&pMain[k++] ==pPattern[j++]);if (pPattern[j] =='\0'){printf("match ok at %d\r\n",i);}if ('\0' ==pMain[k]){break;}} }

用圖表表示暴力搜索算法如下：

目標串：abcabcad

模式串：abcad

下標計數	0 1 2 3 4 5 6 7	?
目標串	a b c a b c a d	?
模式串	a b c a d	第1次比較
匹配情況（o表示匹配，x表示不匹配）	o o o o x	?
?	? a b c a d	第2次比較
?	? x	?
?	??? a b c a d	第3次比較
?	??? x	?
?	????? a b c a d	第4次比較
?	????? o o o o o	?

由此表我們可以知道暴力搜索的時間復雜度大概為：O（目標串長度*模式串的長度）

?

那么暴力搜索算法有沒有改進的空間呢？

答案是肯定的！

仔細分析上表，我們會發現在第一次匹配的時候，目標串和模式串在下標為4的時候發生了不匹配（目標串中是b，模式串中是d）。

因為此時我們已經知道了目標串的前4個字符和模式串中的前4個字符是匹配的（注意：接下來的分析均以此為出發點），所以，其實不用看目標串，只看模式串，我們也能夠“預知”接下來的第2次和第3次比較是肯定會失敗的。

因為第2次比較是把模式串往右移一位，模式串的前3位（abc）要和目標串中下標從1開始的3位（bca）進行比較，目標串中下標從1開始的3位和模式串中下標為1開始的3個字符（bca）是匹配的。因為bca不匹配abc,所以第2次比較不匹配。

再看第3次比較，將模式串往右移動2位，模式串的前2位（ab）要和目標串中下標從2開始的2位（ca）進行比較，目標串中下標從2開始的2位（ca）和模式串中下標從2開始的2位（ca）是匹配的。因為ca不匹配ab，所以第3次比較也不匹配。

而且我們可以知道在第4次比較中，第0個字符是匹配的。因為在第4次比較中，模式串的第0位要和目標串的第3位進行比較，目標串的第3位和模式串的第3位是相同的，所以只要看模式串的第0位和第3位是否相同，我們就能知道第0個字符的匹配情況，在這里模式串的第0位和第3位是相同的。

?

3.?????? KMP算法的思想

首先為了簡化說明，統一稱謂，我們給出下列定義：

字符串的前綴：從主串下標0開始的子串稱為主串的前綴。

?

字符串的后綴：從主串下標大于0的位置到結尾的子串稱為主串的后綴。

（前綴和后綴都是主字符串的一部分，而不能是全部）

?

兩個字符串的匹配：兩個字符串中每一位都一一對應的相同，我們稱這兩個字符串匹配。顯然匹配的兩個字符串等長。

?

對于一個給定的字符串，我們可以搜索它的所有前綴、后綴匹配的序列。對于前綴和后綴匹配的部分我們稱之為首尾重復。所有匹配的前綴、后綴序列稱為所有重復序列。

例如對于字符串aabaa。我們可以列出它的所有前綴和后綴：

主串	ababa
所有前綴 (長度從小到大)	a
	ab
	aba
	abab
所有后綴 (長度從小到大)	a
	ba
	?aba
	baba

所以對于字符串ababa來說：它的首尾重復有a(第一個字符和最后一個字符都是a),aba（前3個字符和最后3個字符都是aba）。如果我們用重復的長度來組成一個序列的話，那么ababa的所有重復序列為{1,3}。

?

歸納一下上面的分析過程，可以得到更一般的結論：

如果目標串和模式串在第m位（模式串的第m位）發生了不匹配，只需要分析模式串的前m位，我們就可以知道，在接下來的后1次比較中，前面長度為m-1的字符是否和目標串匹配。

（如果模式串的前m位中，長度為m-1的前綴和后綴匹配，那么此次比較中前面長度為m-1的字符和目標串匹配，反之不匹配）

舉例：

目標串為D₁D₂ D₃ D₄ D₅ D₆

模式串為A₁A₂ A₃ A₄ A₅ A₆

下標： ? ?0 ?1 ? ?2 ? ?3 ? 4 ? ?5

在下標為5的位置發生了不匹配（目標串中是D₆,模式串中是A₆），如果模式串中A₁ A₂A₃ A₄ （長度為4的前綴）匹配A₂ A₃ A₄ A₅（長度為4的后綴）,那么接下來的一次匹配中（把模式串右移一位）模式串的前面4位就能和目標串匹配了。且前面4個字符的比較可以直接跳過，直接比較模式串的A₅和目標串的D₆。

如果模式串中A₁ A₂ A₃A₄ 不匹配A₂ A₃ A₄A₅,那么我們可以知道接下來的一次匹配肯定是會失敗的。我們可以跳過這次比較。繼續看模式串（A₁ A₂ A₃ A₄ A₅）的長度為3的前綴是否匹配長度為3的后綴。

重復這一步驟，我們可以一直檢查到長度為1的前綴和后綴是否匹配。

?

將這些能夠匹配的前綴、后綴對記錄下來，我們就知道在發生不匹配時，我們的模式串該右移到什么位置來和目標串繼續進行匹配（以例子中的情況來說，如果長度為4的前綴、后綴對匹配，那么模式串應該右移1位再繼續比較；如果長度為3的前綴、后綴對匹配，那么模式串應該右移2位再繼續比較），而且繼續匹配時，指向目標串的指針是不需要回溯的（繼續從發生不匹配的位置開始進行比較）。

所以，我們可以將模式串的每一位對應的前綴、后綴對（可能會有不止一對）先計算保存起來，在匹配過程中，在哪一位發生了不匹配，我們查表就可以知道應該將模式串右移到什么位置來繼續進行比較。這就是KMP算法的基本思想。

?

接下來的工作轉化為：求模式串中每一位對應的所有重復序列。

?

我們先使用肉眼查看的方式統計模式串的每一位對應的所有重復序列：

模式串：aabaabaa

第1位對應的所有重復序列：{0}

第2位對應的所有重復序列：{1}（在字符串aa中長度為1的前綴、后綴對匹配）

第3位對應的所有重復序列：{0}

第4位對應的所有重復序列：{1}（在字符串aaba中長度為1的前綴、后綴對匹配）

第5位對應的所有重復序列：{1,2}（在字符串aabaa中長度為2的前綴、后綴對匹配）

第6位對應的所有重復序列：{3}(在字符串aabaab中長度為3的前綴、后綴對匹配)

第7位對應的所有重復序列：{1,4}(在字符串aabaaba中長度為1和4的前綴、后綴對匹配)

第8位對應的所有重復序列:{1,2,5}(在字符串aabaabaa中長度為1,2,5的前綴、后綴對匹配)

?

現在假設模式串aabaabaa在和目標串匹配過程中，前面7位都是匹配的，第8位發生了不匹配，我們查第7位對應的重復序列表，取得的最大數是4，那么接下來的比較應該從目標串的第8位和模式串的第5位開始。（之所以選擇最大數4是因為這樣模式串移動的位置最小，如果我們一上來就選擇1，那么模式串移動的位置將比4大，可能會遺漏前面能夠匹配的位置）

?

接下來目標串的第8位和模式串的第5位比較可能有兩種情況：

1 匹配。

2 不匹配。

我們先討論不匹配的情況，此時很顯然我們看表里面比4小的數是1，所以我們應該拿目標串的第8位和模式串的第2位進行比較。

我們在看匹配的情況，如果目標串的第8位和模式串的第2位匹配了（注意：這是前提），而在后面的某一個位置M處（模式串的位置）發生了不匹配，那么我們應該查模式串第M位對應的重復序列表來決定下一次的比較位置了，而可以忽略這里第7位對應的重復序列表中其余的序列。（在這里也就是表現在可以不管重復序列1，可以不用去比較目標串的第8位和模式串的第2位了）。

?

為什么可以省略掉其余重復序列的比較？我們給出證明。

?

已知：

模式串的第A位對應的重復序列表為：{n,m}(n<m)

結論：

如果模式串在和目標串的比較過程中在第A位之后的1位發生了不匹配，此時將模式串第m位后的1位來和目標串進行匹配，如果在比較k個字符后發生了不匹配，此時我們可以查看m+k位對應的重復序列表，而不需要管第A位對應的重復序列表的下一個重復序列n。

?

假如m+k組成的模式字符串（的一部分）在位置B處發生了不匹配，我們只需要考慮m+k字符串對應的重復序列表，而不需要再考慮n+1位在目標串的位置A處是否能夠匹配的上。

分析如下：

n+k長度的模式串和目標串比較有兩種結果：

1 匹配。

2 不匹配。

如果不匹配，那么我們自然可以跳過n在位置A的比較。

如果能匹配，從“第1行”和“第2行”可知模式串開頭n+k長度的子串是開頭m+k長度的子串的后綴，而這兩個字符串又都是從模式串開頭起始的，所以短串（n+k子串）是長串（m+k子串）的前綴。因為n+k子串既是m+k子串的前綴，也是m+k子串的后綴，所以n+k是m+k子串的一個重復序列。所以在考慮位置B對應的m+k子串的所有重復序列時，如果前面位置A的n前綴是一個能夠匹配的位置時，那么n前綴也會以n+k的形式包含在m+k子串的所有重復序列中。這樣我們可以放心的只管m+k子串的所有重復序列，而不用在位置B不匹配時，又回溯目標串從位置A處開始和n前綴的后一個字符進行比較。

KMP算法就是這樣避免了回溯目標串的指針。如果目標串是在文件中，我們只需要順序地一個字符一個字符讀取就可以了。

?

前面講到了需要計算出模式串中的每一位對應的所有重復序列，這樣才能在匹配過程中一旦發現不匹配就可以通過查表來確定接下來該把模式串往后移動到什么位置再繼續和目標串的失配字符繼續比較。但是模式串的每一位對應的重復序列的個數是不一樣的，以上面的模式串：aabaabaa為例，第7位的重復序列有2個，第8位的重復序列有3個。我們能不能將目前這種不定長二維重復序列表進行簡化呢？

答案是肯定的！

我們來看以下命題：

已知：

一個字符串的所有重復序列為{m₁,m₂,…m_N-1,m_N}（m₁< m₂< … < m_N-1 < m_N）。

結論：

該字符串的長度為m_N的前綴串的所有重復序列為{ m₁,m₂,…m_N-1}。

?

因為：

1.????????“前 m_N-1個字符”和“后m_N-1個字符”匹配；

2.????????“后m_N-1個字符”其實就是“后m_N個字符”的后綴；

3.????????“后m_N個字符”和“前 m_N個字符”匹配。

所以：

m_N-1是“前 m_N個字符”組成的字符串的一個重復序列。

同理可得：m₁,m₂,…m_N-1都是“前 m_N個字符”組成的字符串的重復序列。

接下來使用反證法證明這些重復序列是所有的重復序列。

假設在“前 m_N個字符”組成的字符串中存在另外一個重復序列m_k,那么在“前 m_N個字符”組成的字符串中，前面m_k個字符匹配最后m_k個字符。而在主串中前面m_N個字符匹配最后m_N個字符，所以在主串中前面m_k個字符匹配最后m_k個字符。所以m_k也是主串的一個重復序列。這與已知條件：{m₁,m₂,…m_N-1,m_N}是字符串的所有重復序列矛盾。

假設不成立，故命題得證。

?

遞歸運用以上命題，我們就可以知道：

如果：

一個字符串的所有重復序列為{m₁,m₂,…m_N-1,m_N}（m₁< m₂< … < m_N-1 < m_N）。

那么：

該字符串的長度為m_N的前綴串的所有重復序列為{m₁,m₂,…m_N-1}。

該字符串的長度為m_N-1的前綴串的所有重復序列為{m₁,m₂,…m_N-2}。

………………

該字符串的長度為m₂的前綴串的所有重復序列為{m₁ }。

該字符串的長度為m₁的前綴串的所有重復序列為{0}（該前綴沒有可匹配的重復序列）。

這樣我們就可以優化模式串中每一位對應的重復序列表的存放方式，將二維表變成一維線性表，仍假設一個字符串的所有重復序列為{m₁,m₂,…m_N-1,m_N}，我們可以這樣組織一維線性表：

位置索引(1為起始下標)	該位置對應的最長重復序列
1	……
……	……
m1	0
……	……
m2	m1
……	……
mn-1	m n-2
……	……
mn	mn-1
……	……
字符串長度	mn

在此一維線性表中，只要我們知道了模式串對應的最大的重復序列（m_n），我們就可以用這個最大的重復序列做索引，順藤摸瓜，依次找到該模式串的所有重復序列。

?

回顧前面我們通過肉眼判斷出來的模式串每一位的重復序列表

模式串：aabaabaa

第1位對應的所有重復序列：{0}

第2位對應的所有重復序列：{1}（在字符串aa中長度為1的前綴、后綴對匹配）

第3位對應的所有重復序列：{0}

第4位對應的所有重復序列：{1}（在字符串aaba中長度為1的前綴、后綴對匹配）

第5位對應的所有重復序列：{1,2}（在字符串aabaa中長度為2的前綴、后綴對匹配）

第6位對應的所有重復序列：{3}(在字符串aabaab中長度為3的前綴、后綴對匹配)

第7位對應的所有重復序列：{1,4}(在字符串aabaaba中長度為1和4的前綴、后綴對匹配)

第8位對應的所有重復序列:{1,2,5}(在字符串aabaabaa中長度為1,2,5的前綴、后綴對匹配)

我們可以通過上面的方法將結果改變成按照一維線性表的方式存放：

位置索引(1為起始下標)	該位置對應的最長重復序列	所有重復序列
1	0	無重復序列
2	1	下標1=0
3	0	無重復序列
4	1	下標1=0
5	2	下標2=1 下標1=0
6	3	下標3=0
7	4	下標4=1
8	5	下標5=2 下標2=1 下標1=0
?	下文要用到的next數組	?

該表也很直觀地驗證了我們上面的命題的正確性。

4.?????? KMP算法的代碼實現

通過以上分析我們可以看出，使用KMP算法關鍵是要獲得模式串中每一位對應的最長重復序列。我們把得到的數值保存在一個名為next的數組中，next數組的長度和模式串的長度一樣。

假設我們知道next[A]的值為m(最長重復序列)，那么next[A+1]的值為多少呢？

?

?

分為兩種情況：

如果模式串的p[A+1] == p[m+1]，那么next[A+1] = m+1。

如果模式串的p[A+1] != p[m+1]，那么我們應該找下一個次長的重復序列來測試，位置A處的下一個次長重復序列，通過上面的“命題”，我們知道就是next[m]。所以，我們接下來的工作將轉為測試p[A+1]是否==p[next[m]+1]。這樣就形成了一個遞歸，遞歸的結束是要么找到p[A+1]==p[n+1]（n是位置A的一個重復序列），要么所有的重復序列之后的一個字符都不能匹配上，此時next[A+1] = 0。

回顧上面模式串：aabaabaa的next數組構造方式，位置3的next[3]計算過程為：

判斷p[3]是否==p[next[2]+1],p[3]!=p[2]，所以繼續判斷p[3]是否==p[next[next[2]]+1]

P[3]!=p[1]，1已經是最小長度了，所以next[3]=0。

位置7的next[7]計算過程為：

判斷p[7]是否==p[next[6]+1],p[7]==p[4]，所以next[7]=next[6]+1=4。

我們將以上過程用代碼實現（注意：代碼中的下標從0開始）：

void GetNext(char *p,int nLen, int *next) {next[0] = 0;for (inti = 1; i < nLen; i++){int tmp = next[i-1]; FLAG1:if (p[tmp] ==p[i]){next[i] =tmp + 1;}else if (0 == tmp){next[i] = 0;}else{tmp = next[tmp-1];goto FLAG1;}} }

以上原始代碼是嚴格按照我們前面的分析寫出來的，用以上代碼求模式串“aabaabaa”，得到的數值和前面我們肉眼觀察的值一致。

特別需要注意的是代碼里面是以0為起始下標的，而前面表格中是以1為起始下標的。

?

我們在實際使用kmp算法時，是在發現不匹配的位置（假設下標為A處）時，應該去找前面從下標0到下標A-1組成的字符串的最長重復序列，然后將模式串進行適當的移動。所以上面例子中的模式串“aabaabaa”的next數組應該做一點調整：

位置索引i(0為起始下標)	對應的字母	Next[i]
0	a	-1
1	a	0
2	b	1
3	a	0
4	a	1
5	b	2
6	a	3
7	a	4

(注：next[0] = -1，有雙重意義，一是為了簡化代碼分支；二是因為實際匹配中，如果在第0位發生了不匹配，目標串從數學意義上就應該是和模式串的-1進行比較，也就是目標串的指針應該往后挪1位和模式串的第0位進行比較。)

?

相應的求next數組的代碼修改如下：

void GetNext2(char *p,int nLen, int *next) {next[0] = -1;next[1] = 0;for (inti = 2; i < nLen; i++){int tmp = next[i-1]; FLAG1:if (-1 == tmp || p[tmp] ==p[i-1]){next[i] =tmp + 1;}else{tmp = next[tmp];goto FLAG1;}} }
為了驗證代碼的正確性，我寫了一段暴力搜索的代碼來求一樣next數組：

void Force(char *p,int i, int *pNext) {for (intlen = i-1; len >= 0; len--){if (memcmp(p, &p[i-len],len) == 0){pNext[i] =len;break;}} } void ForceNext(char *p,int nLen, int *pNext) {pNext[0] = -1;int i = 1;for (; i < nLen; i++){Force(p,i, pNext);} }
可以寫測試代碼來驗證這兩種方法得到的結果是否一致。

?

接下來我們對GetNext2函數繼續調整，這段代碼使用了goto語句，從形式上來說很不美觀，也不夠結構化。另外我們先指定的next[1]=0也是多余的，后面的for循環可以保證next[1]=0，只需要將for的起始i改為1。

void GetNext3(char *p,int nLen, int *next) {next[0] = -1;int tmp = -1;for (inti = 1; i < nLen;){if (-1 == tmp || p[tmp] ==p[i-1]){next[i] =tmp + 1;tmp = next[i];i++;}else{tmp = next[tmp];}} }
上述代碼可以更精簡一點：

void GetNext3(char *p,int nLen, int *next) {int tmp = next[0] = -1;for (inti = 1; i < nLen; ){if (-1 == tmp || p[tmp] ==p[i-1]){next[i++] = ++tmp;}else{tmp = next[tmp];}} }

這段代碼已經和網上很多地方的代碼類似了，我們可以用這段代碼求出next數組，并真正使用到kmp算法中。

接下來實現kmp算法的代碼：

char* KmpMatch(char *pDest,char* pPattern) {char *pFind =NULL;int nLen = strlen(pPattern);int *pNext =new int[nLen];int i = 0;int j = 0;if (!pNext){return NULL;}GetNext3(pPattern,nLen, pNext);while (pDest[i] !='\0' && pPattern[j] != '\0'){if (pDest[i] ==pPattern[j]){i++;j++;}else{j = pNext[j];if (j == -1){j = 0;i++;}}}if (j ==nLen){pFind = &pDest[i-j];}if (pNext){delete pNext;pNext = NULL;}return pFind; }
該代碼中while循環里面的if/else分支可以進行一些合并：

while (pDest[i] !='\0' && j < nLen) {if (j == -1 ||pDest[i] ==pPattern[j]){i++;j++;}else{j = pNext[j];} }

至此整個KMP算法就講的差不多了。

接下來我們要講一個KMP算法的特例，以及對KMP算法的改進。

?

5.?????? KMP算法改進

對于特例模式串aaaaa，它的next數組我們用上面的代碼可以計算出：

next[5] = {-1,0,1,2,3}。

我們看一下根據這個next數組進行匹配的情況，假設目標串為aaaacxxxx。

如下圖：

下標計數（從0開始）	0 1 2 3 4 5 6 7 8	?
目標串	a a a a c x x x x	?
模式串	a a a a a	第1次比較，第4位不匹配
（o匹配，x不匹配）	o o o o x	next[4]=3接下來從模式串的第3位開始比較
?	? a a a a a	第2次比較，第3位不匹配
?	? o o o x	next[3]=2接下來從模式串的第2位開始比較
?	??? a a a a a	第3次比較，第2位不匹配
?	??? o o x	next[2]=1
?	????? a a a a a	第4次比較，第1位不匹配
?	????? o x	?
?	????? ??a a a a a	第5次比較，第0位不匹配
?	?????? ?x	?

分析一下這個過程，我們會發現，第1次比較在第4位失配，也就是目標串在第4位不是a，而我們的模式串里面的每一位都是a，那么只要是比較的時候會比較到目標串的第4位則匹配必然是會失敗的。也就是說我們接下來第2,3,4,5次比較其實早已注定是無用功。

根據之前的next數組計算方法得到next[4]=3，也就是說如果在第4位失配的話，應該用模式串的第3位來繼續比較，但是在這里，模式串的第4位和第3位都是a，如果第4位和目標串不匹配，那么第3位和目標串肯定也是不匹配的。

?

所以我們應該改進next數組的計算方法，在找到失配位置之前的最長重復子串時，還要保證最長重復子串接下來的一個字符不等于失配位置的模式串字符。這一點最早是D.E.Knuth（TAOCP的作者）發現的，其實KMP算法原本是MP算法（J.H.Morris和V.R.Pratt），D.E.Knuth改進MP算法之后，將自己的名字加在前面，成為KMP算法。

?

具體到模式串aaaaa來說，我們在計算next[4]時，不僅要看到模式串的前面4個字符aaaa的最大重復子串為3，還要看下標為3的字符是否和和下標為4的字符是否相等，如果相等，那么3就是不合格的最大重復子串（必然導致匹配失敗）。我們對GetNext3函數進行改進：

void GetNext4(char *p,int nLen, int *next) {int tmp = next[0] = -1;for (inti = 1; i < nLen; ){if (-1 == tmp || p[tmp] ==p[i-1]){if (p[i] != p[tmp+1]){next[i++] = ++tmp;}else{next[i++] = next[++tmp];}}else{tmp = next[tmp];}} }
對于這個新的條件，我們依然可以改進我們的暴力搜索next數組代碼來進行驗證：

void Force2(char *p,int i, int *pNext) {pNext[i] = -1;for (intlen = i-1; len >= 0; len--){if (memcmp(p, &p[i-len],len) == 0 && p[i] != p[len]){pNext[i] =len;break;}} } void ForceNext2(char *p,int nLen, int *pNext) {pNext[0] = -1;int i = 1;for (; i < nLen; i++){Force2(p,i, pNext);} }

改進后的next數組對KMP算法的主體匹配部分不影響，代碼保持不變。

?

對于函數GetNext4，if分支的前一部分代碼next[i++] = ++tmp;比較容易理解。

if (p[i] != p[tmp+1]){next[i++] = ++tmp;}else{next[i++] = next[++tmp];}

對于else部分的代碼next[i++]= next[++tmp];我們仍然是心里不踏實。這樣寫對嗎？實驗出來的正確性是否只是簡單情況下的巧合？是否有其他特殊情況是我們沒有考慮到的？

為了讓大家放心，我們來嘗試證明。

首先，我們明確改進后的next數組有兩個前提條件：

條件1： next數組中的數值是前面部分子串的最長重復序列,如果next[i]=tmp，則模式串中從下標0到i-1的子串中，前面tmp位和最后tmp位是一樣的（重復序列）。

條件2：如果next[i] = tmp，則模式串中的p[tmp] != p[i]。

?

現在，已知模式串p的next數組中next[i-1]=tmp，問next[i] = 多少？

畫圖如下：

?

?

如果p[tmp] == p[i-1]且p[tmp+1] != p[i]，則按照代碼中的流程

next[i++] = ++tmp;

這和改進之前的代碼一樣，我就不再解釋了。

如果p[tmp] == p[i-1]且p[tmp+1] == p[i](違背了條件2)，我們分析一下這時候該怎么得到next[i]？

因為：p[tmp] == p[i-1]

所以：tmp+1是next[i]的最長重復序列，只是因為p[tmp+1] == p[i](違背了條件2)，所以我們不能寫next[i] = tmp+1。

既然tmp+1不滿足，那么我們就應該考慮next[i]的次長重復序列，而根據前面的命題，次長的重復序列就是next[tmp+1]。

令next[tmp+1] = n（如上圖紫色部分所示），next[tmp+1] =n滿足條件1和條件2。

根據條件2得：p[tmp+1] != p[n]。

而已知條件中：p[tmp+1] ==p[i]。所以p[n] != p[i]（滿足條件2）。

n是next[i]的次長重復序列（最長重復序列tmp+1已經不滿足條件2），且n滿足條件2。

所以next[i] = n = next[tmp+1]。

else分支中的代碼得證。?

6.?????? 使用KMP算法在目標字符串中查找所有匹配的位置

我們上面演示的代碼只是在目標字符串中查找到第一個匹配的位置后就返回了，如果要想匹配所有的位置，我們需要將模式串最后的’\0’結尾字符也考慮進去（對于查找二進制串的要做相應的1位擴充）。構造的next數組元素要多一個，在做KMP查找的時候找到第一個匹配處并不退出循環，而是繼續查找下去。

相應代碼如下(注意：本文中演示的KMP算法代碼不能直接用于二進制串搜索)：

void KmpLoopMatch(char *pDest,char* pPattern) {char *pFind =NULL;int nLen = strlen(pPattern);int i = 0;int j = 0;int nFind = 0;int *pNext =new int[nLen+1];if (!pNext){return;}printf("Find \"%s\" in \"%s\":\r\n",pPattern, pDest);GetNext3(pPattern,nLen+1, pNext);while (pDest[i] !='\0' && j <= nLen){if (j == -1 ||pDest[i] ==pPattern[j]){i++;j++;if (j ==nLen){printf("Match at: %d\r\n",i-j);nFind++;}}else{j = pNext[j];}}if (pNext){delete pNext;pNext = NULL;}printf("All find %d position(s).\r\n",nFind); }

7.?????? 使用Z-BOX算法計算next數組

在http://blog.csdn.net/sun2043430/article/details/8784853一文中，我們講述了Z-BOX算法。我們可以根據一個字符串的Z-BOX數值，計算出該字符串的next數組，而且是改進之后的next數組。

針對字符串p的Zi(p)值，其含義是從位置i處有多長的子串和p的前綴匹配。例如對于字符串aabaaab，Z3(p)的值（下標從0開始）= 2。因為p[3,4] =p[0,1] = “aa”。并且p[5] !=p[3]。所以我們可以知道這個字符串的next數組在下標5位置的next[5] = 2。根據這一思路我們可以完成Z-BOX值到next數組值的轉化，需要注意的是，可能有不止一個Z-BOX值指向了同一個位置的next值，例如abaxabac，Z4(p) = 3，Z6(p) = 1。根據Z4(p) = 3，我們可得next[4+3] = 3；根據Z6(p) = 1，我們可得next[6+1] = 1。這樣next[7]就算出了2個不同的值，但很顯然我們需要的是較大的數值，也就是3。根據這一分析，我們在做Z-BOX數值到next數值的轉換時，需要從后往前處理，這樣大的數值，可以覆蓋小的數值，同時對于那些沒有計算到的空位，我們需要將其填寫為0或者-1，如果該位和字符串開頭的字符不同則填0，如果相同則填-1。對應的轉換代碼如下：

void ZBox2KMPNextArray(const char *p, intzbox[], int nLen, int next[]) {next[0] = -1;for (inti = 0; i <=nLen; i++ ){if (p[i] ==p[0]){next[i] = -1;}else{next[i] = 0;}}for (inti = nLen-1;i > 0; i--){int tmp = zbox[i];if (0 != tmp){next[i+tmp] =tmp;}} }?

這個使用Z-BOX值計算next數組的方法易于理解，寫代碼也比較容易。但使用Z-BOX數值來計算next數組需要額外的空間來保存Z-BOX數組中間值。在算法的時間復雜度方面，Z-BOX數組的計算時間是線性的，從Z-BOX值轉換到next數組的時間也是線性的，整體上的時間復雜度為線性時間。

對于不熟悉Z-BOX算法的讀者，請參閱上面給出的鏈接。使用Z-BOX值計算next數組的好處是從思路上完全避免了遞推計算中各種數學證明，直觀易懂。

五、???????總結

至此，KMP算法的整體思路、推導過程和代碼實現都講完了。整個文章一路寫下來，基本上是一個學習、思考、從質疑到確定的過程，按照我自己對KMP的理解，對我認為不容易理解，不講解清楚、不證明其正確性不能令自己信服的地方花費了很多功夫進行文字說明、圖表演示、邏輯證明。雖然篇幅龐大，但恐仍然有不及之處，另外篇幅冗長可能給讀者的閱讀和理解也帶來一定的干擾性。再此表示抱歉，并懇請各位讀者不吝賜教！

劉未鵬在其《知其所以然》系列文章中，就陳述了目前算法教學、書籍中普遍存在的弊端，即只給結論，不給思考過程，只授人以魚，不授人以漁的狀況。他認為算法、數學的教學需要講解出整個思維的過程，如何從已知一步一步遞進到結論。我的這篇文章本著這樣的想法，力求從簡單的、易懂的已知部分，一步一步到達終點，但中間有些地方，實在是因為本人能力有限，而不得不從結論部分來倒推、揣摩其原理，當然這也是學習過程中普遍采用的一種方法。

最后，我在嘗試寫這篇kmp算法文章時，參閱了大量網上的文章，如july_v，matrix67，以及以下這篇未署名的文章：http://uriah.diandian.com/post/2012-07-23/40029493444。其他的文章和作者我就不一一列出了，再次一并表示感謝，并特別感謝劉未鵬及其啟發思維的好文章！

本文所述KMP算法源碼可在這里下載：

http://download.csdn.net/detail/sun2043430/5259164

總結

以上是生活随笔為你收集整理的【模式匹配】之 —— KMP算法详解及证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。