經典串匹配算法（KMP）解析

no_mkd

一.問題重述

現有字符串 S1，求 S1 中與字符串 S2 完全匹配的部分，例如：S1 = "ababaababc", S2 = "ababc"

那麼得到匹配的結果是 5（S1 中的"ababc"的 a 的位置），當然如果 S1 中有多個 S2 也沒關係，能找到第一個就能找到第二個。。

最容易想到的方法自然是雙重循環按位比對（BF 算法），但在最壞的情況下 BF 算法的時間複雜度達到了 m * n，這在實際應用中是不可接受的，於是某 3 個人想出來了 KMP 算法（KMP 是三個人的名字。。）

二.KMP 算法具體過程

（先不要著急想看 KMP 算法的官方定義，很難看懂的，所以這裡乾脆不給定義了。。）

認真審視一下 S2 = "ababc"，很重要的一點是：開頭出現了 ab，中間部分又出現了 ab（先記住這個細節）

現在假定一個時刻：

此時 abab 部分匹配成功，S1 的位置指針指向了 a，當前正在做的事情是 a 與 c 比對，結果是匹配失敗

如果是 BF 算法，那麼下一步是 S1 的位置指針回溯到第二位的 b，S2 的位置指針重置到開頭的 a，然後 b 與 a 比對，然後。。
如果是 KMP 算法，那麼下一步是 S1 位置指針不變（指向 a），然後查跳轉表（next 表）得到跳轉值 2，再把 S2 的指針移動到第二個 a 上，接下來比對 a 與 a，然後。。

KMP 的步驟看不明白沒關係，畢竟我們還沒有解釋跳轉表（next 表）是什麼，不過在這裡我們只用關注結果就好了：

BF 算法中 S1 的指針向左移動了（回溯）
KMP 算法中 S1 的指針沒有往回走（無回溯）

因為 KMP 算法不存在回溯過程，所以節省了不少時間（S1 的指針只需要從頭走到尾就可以了）

再看看 KMP 算法的核心——跳轉

為什麼可以跳轉？注意觀察一下 S2 = "ababc"，這個串的特點是：開頭出現了 ab，中間部分又出現了 ab（還記得這個細節嗎），詳細解釋一下：

如果 S2 末尾的 c 與 S1 的第 k 位匹配失敗，我們可以推斷出兩個信息：

本趟匹配失敗了（c 匹配失敗意味著 S1 中的的某一部分不能匹配 S2）
S1 中第 k 位前的 4 位一定是 abab（只有 S2 中的 abab 與 S1 中的某一部分匹配成功後才可能出現 S2 的 c 與 S1 第 k 位的比對）

如果我們忽略第 2 點，那麼下一步是 S1 指針回溯，也就是 BF 算法將要做的；如果我們抓住第 2 點，再加上 S2 串的特點：

開頭出現了 ab，中間部分又出現了 ab（再重申一遍）

就可以得到 KMP 算法（相當於 S1 中第 k 位之前的 ab 已經和 S2 開頭的 ab 匹配了，所以可以直接跳轉到 S1 的第 k 位與 S2 的第 3 位 a 比對）

好像有點明白了，那麼這個跳轉值 2 是怎麼得到的？多舉一些例子：

S2 = "aba"最後一位的跳轉值為 0
S2 = "abaa"最後一位的跳轉值為 1
S2 = "abcabc"最後一位的跳轉值為 2

發現什麼了嗎？沒錯，我們求 S2 中第 x 位（此處的 x 是從 0 開始算的）的跳轉值的過程是這樣的：

如果 x = 0，那麼 S2[x] 的跳轉值為 -1（首元的跳轉值為 -1）
如果 x = 1，那麼 S2[x] 的跳轉值為 0（第二個元素的跳轉值為 0）
如果 S2[x - 1] = S2[0]，那麼 S2[x] 的跳轉值為 1
如果不滿足第 3 條，那麼跳轉值為 0
如果 S2[x - 1] = S2[0] 並且 S2[x - 2] = S2[1]，那麼 S2[x] 的跳轉值為 2
如果 S2[x - 1] = S2[0] 並且 S2[x - 2] = S2[1] 並且 S2[x - 3] = S2[2]，那麼 S2[x] 的跳轉值為 3
。。。

人用眼睛按照上面的方法「目測」跳轉值是最快的，但同樣的過程用於計算機的話就不那麼容易實現了，計算機有計算機喜歡的方式，一篇簡短的博文解釋了這種方式

簡單的說就是——「遞推」，即由已知的首項為 -1，第二項為 0，遞推得到後面所有項，詳細過程不再贅述，上面的鏈接博文寫的非常清楚

下面可以得出 KMP 算法的具體過程了：

根據模式串 S2 構造跳轉表（next 表）
從 S1 頭開始比對，查 next 表得跳轉值，S1 指針向右移動繼續比對，直至 S1 末尾

說白了又是在用空間換時間（next 表佔用的空間），當然，在此算法中 next 表是長度等於模式串 S2 長度的線性表而已，並不需要太多空間

三.實現 next 函數

next 函數用來構造 next 表（跳轉表），如何構造 next 表才是 KMP 算法的關鍵（如果不關注 KMP 的證明過程的話。。）。我們可以按照鏈接博文的方式自己實現 next 函數：

//參考例子：http://blog.sina.com.cn/s/blog_96ea9c6f01016l6r.html
#include<stdio.h>
void getNext(char a[], int n, int next[]){
int i, j;
next[0] = -1;//首元跳轉值為 -1
next[1] = 0;//第二個元素跳轉值為 0

for(i = 2; i &lt; n; i++){
	j = i - 1;
	
	//遞推得到 next 表中剩餘值
	while(j != -1){
		if(a[i - 1] == a[next[j]]){
			next[i] = next[j] + 1;
			break;
		}
		else{
			j = next[j];
		}
	}
}

}
main(){
char a[] = "abaabcac";//模式串 S2
int next[8] = {0};//跳轉表，初始化為全 0
int i;
//構造 next 表
getNext(a, 8, next);
//輸出 next 表
for(i = 0; i &lt; 8; i++){
	printf("%d ", next[i]);
}
printf("\n");

}

當然，上面的 getNext 函數好像仍然不夠高效（雙重循環..），但優點是易於理解。下面看看書上給的 next 函數：

#include<stdio.h>
void getNext(char a[], int n, int next[]){
int i, j;
i = 0;
next[0] = -1;//首元跳轉值為 -1
j = -1;
//遞推得到 next 表中剩餘值
while(i &lt; n){
	if(j == -1 || a[i] == a[j]){
		++i;
		++j;
		next[i] = j;
	}
	else{
		j = next[j];
	}
}

}
main(){
char a[] = "abaabcac";//模式串 S2
int next[8] = {0};//跳轉表，初始化為全 0
int i;
//構造 next 表
getNext(a, 8, next);
//輸出 next 表
for(i = 0; i &lt; 8; i++){
	printf("%d ", next[i]);
}
printf("\n");

}

二者的計算結果是一樣的，但書上給的算法消除了雙重循環，不過這樣做的結果只是讓代碼變得更複雜了而已，沒有任何實質性的優化

什麼？消除了雙重循環竟然沒有提高效率？不可能吧？我們不妨用計數器來驗證一下：

void getNext(char a[], int n, int next[]){
	int i, j;
	int counter = 0;///
next[0] = -1;//首元跳轉值為 -1
next[1] = 0;//第二個元素跳轉值為 0

for(i = 2; i &lt; n; i++){
	j = i - 1;
	
	//遞推得到 next 表中剩餘值
	while(j != -1){
		if(a[i - 1] == a[next[j]]){
			next[i] = next[j] + 1;
			counter++;///
			break;
		}
		else{
			j = next[j];
			counter++;///
		}
	}
}

printf("\n%d\n", counter);///

}
void getNext(char a[], int n, int next[]){
int i, j;
int counter = 0;///
i = 0;
next[0] = -1;//首元跳轉值為 -1
j = -1;
//遞推得到 next 表中剩餘值
while(i &lt; n){
	if(j == -1 || a[i] == a[j]){
		++i;
		++j;
		next[i] = j;
		counter++;///
	}
	else{
		j = next[j];
		counter++;///
	}
}

printf("\n%d\n", counter);

}

P.S. 我們在具體操作的部分（最內部的 if 塊與 else 塊）插入了 counter++;這樣得到的結果才是可比的（算法進行了多少次具體操作）

運行結果如下：

左圖是我們自己實現的 next 函數計數結果，少的這 4 步是外層循環次數的差異（書上的算法是 n 次，我們的算法是 n-2 次），如果我們的算法外層循環次數也是 n 的話，也需要 14 次具體操作（我們只是做了一個簡單的優化）

兩個 next 函數只是形式不同，其內部操作順序是完全相同的，弄清楚了 next 函數，KMP 算法就沒什麼難點了（如果不關心 S1 的指針不用回溯的原因的話，確實只有這一個難點..）

四.KMP 算法正確性的證明

（本文不在此展開，以後理解了的話可能會在此處補充缺失的內容，詳細解釋為什麼 S1 的指針不用回溯，為什麼之前的部分不可能再匹配。。。）

不過單純關注「實現」的話，我們只要理解了 next 函數就完全可以輕鬆實現 KMP 算法了（至於為什麼可以這麼做，怎麼證明這樣做是對的。。這是數學家的事情）

五.總結

KMP 算法的核心是 next 表的構造過程，而構造 next 表的關鍵思想就是「遞推」，理解了這個，完全可以分分鐘寫出 KMP 算法。。

一點題外話：

KMP 算法也有變體，本文討論的是最原始的 KMP 算法，常見的變體有：

next 表首元為 0（而不是 -1），最終得到的結果就是給我們的 next 表中每個元素都 +1，只是約定不同而已（從 0 開始與從 1 開始），並沒有實質性的差別
next 表中有多個 -1（我們的結果中有且只有一個 -1，也就是 next 表首元），這是一種實質性的優化，能有效的提高效率。其實也就是在構造 next 表的時候比我們多做了一步，構造過程變複雜了一點點，但匹配算法的比對次數減少了