在上一節里面我們知道BF算法。

現在我們來講解KMP算法。他的思路如下

每當一趟匹配過程中出現字符比較不等時，不需回溯i指針，而是利用已經得到的“部分匹配”的結果將模式想右滑動進可能遠的一段距離后，繼續比較。

上面那個思路是書上的話，到底是什么意思！！！我們現在用人話來講解。

下面大家跟著我的思路（這節KMP是數據結構的第一個難點，請大家認真對待）

KMP算法的目的：就是為了避免不必要的回溯，這里的不必要的回溯只由模式串（也就是T）決定，與目標串無關（也就是S）。

那么問題來了，什么是不必要的回溯。

上節課將到的BF算法。當匹配不成功時，他就把模式串的指針指向開頭。然后一個個重新匹配，這就是回溯。

這里引進了一個next[]數組，我們先來看下書中這個圖，這圖到底是怎么畫出來的（數據結構C語言版嚴蔚敏2016年12月46次印刷）

這里的next[j]有些教程把這個地方填寫K，意思是告訴大家數據結構里面第三行可以用next[j]或K都可以。

首先我們來看這個j是從1開始，一直到8，那么就有個問題，0呢？

在這本書上，為了更換的說明算法把串的第一個設置為串的大小，并且省略掉最后‘/0’(C/C++里面串結尾都是'/0')

那么我們補充下圖，如下所示：

那么我們來看下，這個next[j](部分教程用K表示)這個到底是怎么填的。

下面就直接告訴大家：

我們看模式串那一行：

j=1時模式串是a，next[j]對應為0(代碼中有交代j==0,在所有的模式串里面第一個都為0，待會在代碼里面會說明這個，現在大家先記著)。

j=2時模式串是b，next[j]對應為1，我們想想，當b比匹配失敗后，我們要回到前面的模式串，那么只能是b前面的a，所以next[j]對應為1。

j=3時模式串是a，next[j]對應為1，這時我們看到了下標3前面的字符是a和b，他們沒有相同的，回溯的話還是a，所以next[j]對應為1。

j=4時模式串是a，next[j]對應為2，這時我們看到下標4前的字符是aba,我們發現首串a和尾串a相同，那么他就是1+1=2。

j=5時模式串是b，next[j]對應為2，下標為5前的字符是abaa，這時首串a，尾串a，那么他就是1+1=2。

j=6時模式串是c，next[j]對應為3，下標為6前的字符是abaab,這時我們發現首串ab，尾串ab，那么他就是2+1=3。

j=7時模式串是a，next[j]對應為1，下標為7前的字符是abaabc，這時我們發現他首串和尾串不相同。那么就是0+1=1。

j=8時模式串是c，next[j]對應為2，下標為8前的字符是abaabca，這時我們發現首串和尾串相同的是a，那么就是1+1=2。

下面我們總結了一個規律：

在KMP算法里面，next的填寫看他前面的串，如果首串和尾串有一個相同則是1+1，如果有兩個則是2+1，三個是3+1，第一個next始終是0。

大家next[j]會畫了吧！

下面我們來看更重要的問題，為什么要next，這個next到底有什么用？

我們現在來看下書中利用模式的next函數進行匹配的過程示例就知道了（圖如下）

這里我們看到：

第一趟當遇到第二個的時候也就是c時與模式里的第二個不一樣，所以退回nex[2]也就是1的地方。

第二趟主串的第一個和模式的第一個都不相等，什么i++，j++。

第三趟我們發現abaab都相等，但下面一個，也就是j=6時，發現不相等，此時next[6]也就是3（待會就解釋這個）

第四趟就匹配成功了。

現在問題來了，為什么可以這么做，這個next到底是什么東西！

我們發現next表示下標為某個數前，相同的字符數+1，這個+1的意思就是指向相同首串的后面那個（比如abaab）ab是首串和尾串都相同的。所以移到第三個，就是是a這個位置。

所以我們貌似發現了一個規律。當匹配不成功時，這個next將回到模式想右滑動進可能遠的一段距離后，繼續比較。

這就是書上：

每當一趟匹配過程中出現字符比較不等時，不需回溯i指針，而是利用已經得到的“部分匹配”的結果將模式想右滑動進可能遠的一段距離后，繼續比較。

的說明。

下面是代碼：

void get_next(SString T, int *next) { 	int i = 1;	next[1] = 0;	int j = 0;	while (i < T[0]) 	{		if (j == 0 || T[i] == T[j]) 		{			++i;  			++j;  			next[i] = j;		}		else 			j = next[j];	}}int Index_KMP(SString S, SString T, int pos) {	// 利用模式串T的next函數求T在主串S中第pos個字符之后的位置的	// KMP算法。其中，T非空，1≤pos≤StrLength(S)。	int next[255];	int i = pos;	int j = 1;	get_next(T, next);	while (i <= S[0] && j <= T[0]) 	{		if (j == 0 || S[i] == T[j]) // 繼續比較后繼字符		{  			++i;  			++j;		}		else // 模式串向右移動			j = next[j]; 	}	if (j > T[0])		// 匹配成功		return  i - T[0];   	else return 0;} // Index_KMP這里我們就可以解釋：為什么模式串第一個next總是一，因為代碼中給它了一個特別的條件。
這代碼不用多解釋，大家也能看懂吧。
下面是KMP的優化：
例如模式‘aaaab’
主串‘aaaarcde’
next圖如下：
j
0
1
2
3
4
5
模式
5
a
a
a
a
b
next[j]
 
0
1
2
3
4
進行匹配的時候我們發現主串的aaaar當到這個r的時候，不匹配，他先回到next[4],然后next[3],next[2],next[1],next[0],
這種是不好的效率，因為我們發現這模式串里面前4個都一樣的。所以我們可以對他修改為這樣。
當計算的過程中如果之前的前綴元素都是相等的話會回溯到前綴元素的next值那里去。
所以，可以改成如下
j
0
1
2
3
4
5
模式
5
a
a
a
a
b
next[j]
 
0
0
0
0
4
所以我們可以對get_next函數進行修改，如下所示：
void get_next(SString T, int *next) { 	int i = 1;	next[1] = 0;	int j = 0;	while (i < T[0]) 	{		if (j == 0 || T[i] == T[j]) 		{			++i;  			++j;  			if (T[i] != T[j])				next[i] = ;			else				next[i] = next[j];		}		else 			j = next[j];	}}