一次性搞懂KMP演算法

如果你是想來看為什么k=next[k],可以翻到第二章的情況2去看；如果你是和我一樣的萌新小白想了解KMP演算法，可以從頭讀起，了解KMP演算法的動機和具體實作原理最后了解其C語言實作細節，

一、動機

??傳統的實作str函式的BF演算法會在子串與主串之間存在許多"部分匹配"的情況下有很多沒有意義的重復步驟，如下圖，

??本文中，主串記為str，在主串中尋找的串記為sub，本文中的子串都是真子串，不包含串本身的子串，也不包含空串,

??sub[0]…sub[k-1]表示由字符sub[0]…sub[k-1]組成的串，

??下圖中，i表示用來遍歷str的指標的位置；j表示用來遍歷sub的指標的位置，

在這里插入圖片描述

??傳統的BF演算法當匹配失敗時，為了能夠遍歷str的所有子串，它會讓i回溯到此輪比較開始位置的下一個位置，讓j回溯到sub的起始位置，繼續比較，但是出于一個考慮，這樣是沒必要的：

??sub它的每一部分都是不相同的,

即
s u b [ 0 ] ! = s u b [ 1 ] , s u b [ 0 ] ! = s u b [ 2 ] , s u b [ 0 ] ! = s u b [ 4 ] sub[0]!=sub[1],sub[0]!=sub[2],sub[0]!=sub[4] sub[0]!=sub[1],sub[0]!=sub[2],sub[0]!=sub[4]
??而我們的第一輪比較一直走到x才結束，這說明str的前五個字符一定和sub是相等的，

即
s t r [ i ] = = s u b [ i ] , f o r ( i = 0 , 1 , 2 , 3 , 4 ) str[i]==sub[i], for(i=0,1,2,3,4) str[i]==sub[i],for(i=0,1,2,3,4)

??那么一定有
s u b [ 0 ] ! = s t r [ 1 ] , s u b [ 0 ] ! = s t r [ 2 ] , s u b [ 0 ] ! = s t r [ 3 ] , s u b [ 0 ] ! = s t r [ 4 ] sub[0]!=str[1],sub[0]!=str[2] ,sub[0]!=str[3] ,sub[0]!= str[4] sub[0]!=str[1],sub[0]!=str[2],sub[0]!=str[3],sub[0]!=str[4]

??這四個不等式說明，我們的比較程序②③④⑤都是沒必要的，因為他們早在①中就可以確定一定會匹配失敗，但是⑥是不能省略的，因為我們沒有判斷sub[0]和sub[5]是否相等，

??所以我們希望我們的演算法可以直接做到把上面的六步簡化為兩步，

在這里插入圖片描述

??有人可能會說，啊這是個特例情況，sub串前面都沒有相同的字符，那么我們接下來就舉一個由相同字符的例子，

在這里插入圖片描述

??步驟②③可以省略，因為abc是不相等的字符，原理同上；
??步驟④⑤其實也可以省略，因為我們的sub串中有兩個相同的字串sub[0]sub[1]和sub[3]sub[4]，我們既然已經在步驟①中比較過了sub[3]sub[4]==str[3]str[4]，那sub[0]sub[1]==str[3]str[4]這不是理所應當的嗎
??所以我們可以把這六個步驟簡化為兩個步驟：

在這里插入圖片描述

??通過觀察這兩個例子，我們有一些直觀的感受:

每次匹配失敗后，指向主串str當前位置的指標i沒必要回退，這個位置記為位置1
因為如果回退了，
- 假如str(sub因為前面匹配都是成功的所以這里說這兩者任意一個都可以)在匹配失敗位置以前的串中沒有相同的字符，那會一路匹配失敗再回到原本的位置1；
- 假設sub前面有一系列相同的字符，那會出現一系列匹配失敗和部分匹配成功，然后也回到原本匹配失敗的位置1，
觀察發現匹配失敗時，指向sub當前匹配位置的指標j要回溯到一個恰當的位置，這個位置由失敗位置之前的串的前后綴相似程度就決定(這里的前后綴的意思是以sub[0]開始的串和以sub[失敗位置-1]結束的串)，

二、next陣列

??下面我們來詳細討論一下j回溯的位置，首先我們觀察到j發生回溯是在str和sub匹配失敗時，那在失敗位置之前的位置str和sub都是匹配成功的(也就是對應字符都是相等的)，因此我們我們的回溯位置僅僅由sub匹配失敗位置之前的串決定，

在這里插入圖片描述

??根據圖中的理解，我們尋找回溯位置是遵照了這樣一個準則，找一個位置以sub[0]開頭的串1，他的結尾字符是sub[j-1]（位置不確定），如果再能找到一個結尾位置是sub[j-1]的串2，并且其開頭字符是sub[0]（位置不確定下標記為x）且要求這倆串相等的，

??如果能做到這件事情，我們就讓j回溯到串1結尾位置的后面的一個位置，我們記這個位置的下標為k,通過串1串2相等，我們計算出x的位置
s u b [ x ] . . . . s u b [ j ? 1 ] = = s u b [ 0 ] . . . s u b [ k ? 1 ] sub[x]....sub[j-1]==sub[0]...sub[k-1] sub[x]....sub[j?1]==sub[0]...sub[k?1]
? k ? 1 ? 0 = = j ? 1 ? x \Rightarrow k-1-0==j-1-x ?k?1?0==j?1?x
? x = j ? k \Rightarrow x=j-k ?x=j?k
這時，在此輪匹配的時候，對匹配失敗位置i以前的串有
s t r [ i ? k ] . . . s t r [ i ? 1 ] = = s u b [ j ? k ] . . . . s u b [ j ? 1 ] str[i-k]...str[i-1]==sub[j-k]....sub[j-1] str[i?k]...str[i?1]==sub[j?k]....sub[j?1]
因此對我們回溯的k位置，有
( s u b [ j ? k ] . . . s u b [ i ? 1 ] = = s u b [ 0 ] . . . s u b [ k ? 1 ] ) (sub[j-k]...sub[i-1]==sub[0]...sub[k-1]) (sub[j?k]...sub[i?1]==sub[0]...sub[k?1])
∧ ( s t r [ i ? k ] . . . s t r [ i ? 1 ] = = s u b [ j ? k ] . . . . s u b [ j ? 1 ] ) \wedge (str[i-k]...str[i-1]==sub[j-k]....sub[j-1]) ∧(str[i?k]...str[i?1]==sub[j?k]....sub[j?1])
? s t r [ i ? k ] . . . s t r [ i ? 1 ] = = s u b [ 0 ] . . . s u b [ k ? 1 ] \Rightarrow str[i-k]...str[i-1]==sub[0]...sub[k-1] ?str[i?k]...str[i?1]==sub[0]...sub[k?1]

??我們就回溯到了這樣一個位置，他前面的子串(以sub[0]起始)和str中當前匹配位置之前的子串(以str[i-k]起始)是相等的，

??我們用一個陣列next來記錄匹配失敗j應當回溯的位置，next[j]表示在j處匹配失敗應該回到的位置

所以，在j處匹配失敗后，應當回到的位置是：
n e x t [ j ] = m a x { k ∣ ( 0 < k < j ) ∧ ( s u b [ 0 ] . . . s u b [ k ? 1 ] = = s u b [ j ? k ] . . . s u b [ j ? 1 ] ) } next[j]=max\left\{ k|(0<k<j) \wedge (sub[0]...sub[k-1] ==sub[j-k]...sub[j-1]) \right\} next[j]=max{k∣(0<k<j)∧(sub[0]...sub[k?1]==sub[j?k]...sub[j?1])}
??但是我們忽略了一件事情，如果不存在這樣的兩個串怎么辦，即做不到找到兩個相等的子串，

??那這時候，我們應該回溯到下標為0的位置，因為這說明不能通過我們上面的技巧來減少j的遍歷次數，所以回到0位置從頭開始遍歷；

??如果在0位置就匹配失敗，我們要讓它回溯到-1位置，即next[0]=-1，這種規定是為了方便我們后面寫代碼好統一兩種進入if陳述句的條件，

??如果是1位置匹配失敗，就只有一個字符不存在子串，直接讓他回溯到0位置，所以我們規定next[1]=0;

所以next陣列的求解公式應該是這樣的
在這里插入圖片描述

??但是這是一個非常數學的求解公式，我們要轉化成一個計算機也能理解的事情，怎么做呢？

??觀察下圖的next陣列：

在這里插入圖片描述

??我們發現next每次增大的話也只能一次增加1，這是自然的，因為每次都只會在后面的子串中多加一個元素，這似乎啟發我們從遞推的角度去想這個問題.

我們假設
n e x t [ i ? 1 ] = = k next[i-1]==k next[i?1]==k
也就是說i-1位置匹配失敗時，j的回溯位置是k，

??根據假設這說明當在i-1位置發生匹配失敗時，會回溯到k位置，也就是說，能找到的兩個最大相等子串的長度是k，

所以有
s u b [ 0 ] . . . s u b [ k ? 1 ] = = s u b [ i ? k ? 1 ] . . . s u b [ i ? 2 ] sub[0]...sub[k-1]==sub[i-k-1]...sub[i-2] sub[0]...sub[k?1]==sub[i?k?1]...sub[i?2]
假設如果有（這種情況記為情況1）
s u b [ k ] = = s u b [ i ? 1 ] sub[k]==sub[i-1] sub[k]==sub[i?1]
立即推
s u b [ 0 ] . . . s u b [ k ] = = s u b [ i ? k ? 1 ] . . . s u b [ i ? 1 ] sub[0]...sub[k]==sub[i-k-1]...sub[i-1] sub[0]...sub[k]==sub[i?k?1]...sub[i?1]
上式等價于
n e x t [ i ] = k + 1 ; next[i]=k+1; next[i]=k+1;
??這太好了，我們如果有next[i-1]=k并且sub[k]=sub[i-1]就能立即退出next[i]的值，

??然后我們可以讓i++,k++，去計算下一個next[]陣列值；

??好，我們現在處理了sub[k]和sub[i-1]相等的情況，如果不相等呢

情況2 sub[k]!=sub[i-1]

??不相等的時候，我們想做的是再找一次符合條件的最大相等子串(除了上次以外的最大)，即找除上一次的兩個最大相等子串外以的sub[0]為開頭，以sub[i-2]為結尾的兩個最大相等子串，然后再比較sub[i-1]和sub[k]，

??這里就體現了這個演算法的巧妙之處了，我們把這個問題轉化一下，

利用已知next[i-1]=k 有
s u b [ 0 ] . . . s u b [ k ? 1 ] = = s u b [ i ? k ? 1 ] . . . s u b [ i ? 2 ] sub[0]...sub[k-1]==sub[i-k-1]...sub[i-2] sub[0]...sub[k?1]==sub[i?k?1]...sub[i?2]
s u b [ i ? 2 ] = s u b [ k ? 1 ] sub[i-2]=sub[k-1] sub[i?2]=sub[k?1]

. .? .?

s u b [ 0 ] = s u b [ i ? k ? 1 ] sub[0]=sub[i-k-1] sub[0]=sub[i?k?1]

??所以我們直接找以sub[0]為開頭，以sub[k-1]為結尾的兩個最大相等子串（也就是在前綴sub[0]…sub[k-1]中找最大相等子串）.

??這樣做合理的，原因如下：

??首先上一次的最大相等子串的長度是k，我們要找長度比它小的最大相等子串，在前綴這樣長度為k的串里頭找出來的最大相等子串長度一定小于k;

??而且由于找的是更小的最大相等子串，以sub[k-1]結尾的子串要在sub[i-k-1]后面的位置找(中間(sub[k]…sub[i-k-2])部分是不用考慮的),并且這些位置的元素本來就和前綴(sub[0]…sub[k-1])中的元素是相等的，我們不會因為是在sub[0]…sub[k-1]中找而漏掉元素或者使得找到的最大相等子串不是除原最大相等子串以外最大的，

??我們可以用一副圖來加深我們的理解，

在這里插入圖片描述

??我們再來回頭看next陣列元素值的意義，

??next[i-1]=k意味著以sub[0]為開頭，以sub[i-2]為結尾的最大相等子串的長度是k，并且由于是以sub[0]開頭的，這兩個子串中以sub[0]開頭的子串的結尾位置的下一個位置的下標就是k，

??所以找以sub[0]開頭以sub[k]結尾的最大相等子串并把以sub[0]開頭的子串的結尾位置的后一個位置賦給k就是k=next[k]，

??所以對情況2的操作就是k=next[k].

??接下來我們再次比較sub[i-1]和sub[k]，如果相等就回到了情況1,

??否則我們仍處于情況2，繼續k=next[k]，

三、C語言實作

首先我們先實作KMP演算法的總體框架

2.1 KMP函式

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

int KMP(char* str, char* sub, int pos)
//pos表示從str串下標為pos的地方開始找
{
	assert(str && sub);//保證不是空指標
	int len1 = strlen(str);
	int len2 = strlen(sub);
	if (len1 == 0 || len2 == 0 || pos >= len1 || pos < 0)
	//保證不是空串且pos值合理
	{
		return -1;
	}
	int* next = (int*)malloc(len2 * sizeof(int));//用來存放next陣列
	int i = pos;//用來遍歷str串
	int j = 0;//用來遍歷sub串
	Getnext(next, sub, len2);//求解next陣列
	while (i < len1 && j< len2)
	//i還沒有走出len1，j還沒有走出len2，說明當還沒遍歷完
	{
		if (j==-1 || str[i] == sub[j])
		//如果字符相等就往下走
        //這里j==-1也可以進if陳述句原因見圖1
		{
			i++;
			j++;
		}
		//如果不等，根據我們的思想j要調到next[j]的位置
		else
		{
			j = next[j];
		}
	}
	free(next);
	next = NULL;
	if (j >= len2)
	//如果j能遍歷完子串，其坐標就是len2(到\0)
	{
		return i - j;//回傳找到的子串的位置
	}
	else
	//長度不夠len2的話還跳出了回圈，都遍歷完了也沒找到
	{
		return -1;
	}
}

圖1：

在這里插入圖片描述

2.2 Getnext函式

void Getnext(int* next, char* sub, int num)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;//記錄當前正在求解的next的下標
	//求next從2開始往后求到num-1
	int k = 0;
	//存盤next[i-1]的值用來做判斷
	while (i < num)
	{
		if ( k==-1 || sub[i - 1] == sub[k])
		//如果相等 推匯出next[i]=k+1 并且把i往后撥一個去計算下一個next, 
        //k也往后撥一個,這樣可以走到上一輪回溯位置的下一個位置，如果此位置的字符和sub[i-1]相等就可以繼續計算next陣列值
        //k==-1也進入if陳述句的解釋見下圖
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}

??這里有一種特殊情況，如果k=next[0]=-1，回溯到了-1去了怎么辦，這樣就不能訪問sub[k]=sub[-1]了，屬于越界訪問，

同理我們用一幅圖來解釋怎么處理這種情況

在這里插入圖片描述

四、改進的KMP演算法

??人們發現，KMP演算法仍然有一定的缺陷，如圖

在這里插入圖片描述

??②③④⑤都是多余的判斷，這是由于sub[0] sub[1] sub[2] sub[3] 都等于sub[4],而sub[4]不等于str[4],所以我們這些回退都是沒有必要的，

??為此我們可以這樣設計，考慮一個nextval陣列，每次計算時，先讓nextval[i]就存放next[i]的值，

然后對比sub[i]和sub[next[i]]這兩個字符

如果相等的話，那說明它回溯到的位置的字符和它一樣，我們讓它的nextval[i]存放這個回溯到字符的nextval[nextval[i]]
如果不相等，nextval[i]就保留next[i]的值即可，

??這樣的話，我們就保證了當原字符和它的回溯字符相等的時候，原字符的回溯位置會變成它回溯字符的回溯字符位置,避免了j一次一次無必要回退，

下圖直觀的講解了計算nextval陣列的動作:

在這里插入圖片描述

我們可以把這個想法用C語言實作如下

void Getnextval(int* nextval, char* sub, int num)
{
	nextval[0] = -1;
	nextval[1] = 0;
	int i = 1;//記錄當前正在求解的next的下標
	//求next從1開始往后求到num-1
	int k = -1;
	//存盤next[i-1]的值用來做判斷
	while (i < num)
	{
		if (k == -1 || sub[i - 1] == sub[k])
		//如果相等 推匯出next[i]=k+1 并且把i往后撥一個 k也往后撥一個
		{
			nextval[i] = k + 1;
			if (sub[k+1] == sub[i])
			{
				nextval[i] = nextval[nextval[i]];
			}
			i++;
			k++;
		}
		else
		{
			k = nextval[k];
		}
	}
}



int KMP(char* str, char* sub, int pos)
//pos表示從str串下標為pos的地方開始找
{
	assert(str && sub);//保證不是空指標
	int len1 = strlen(str);
	int len2 = strlen(sub);
	if (len1 == 0 || len2 == 0 || pos >= len1 || pos < 0)
	//保證不是空串且pos值合理
	{
		return -1;
	}
	int* next = (int*)malloc(len2 * sizeof(int));//用來存放next陣列
	int i = pos;//用來遍歷str串
	int j = 0;//用來遍歷sub串
	Getnextval(next, sub, len2);//求解nextval陣列
	while (i < len1 && j<len2 )
	//當還沒遍歷完
	{
		if (j==-1 || str[i] == sub[j])
		//如果字符相等就往下走
		{
			i++;
			j++;
		}
		//如果不等，根據我們的思想j要調到next[j]的位置
		else
		{
			j = next[j];
		}
		//我們知道有可能j一直往回回溯
		//回溯到了j=next[j]=0,
		//然后0位置還是不相等就回溯到了j=next[0]=-1的地方
	}
	free(next);
	next = NULL;
	if (j >= len2)
	//如果j能遍歷完子串，其坐標就是len2(到\0)
	{
		return i - j;//回傳找到的子串的位置
	}
	else
	//長度不夠len2的話還跳出了回圈，都遍歷完了也沒找到
	{
		return -1;
	}
}
int main()
{
	int ret = KMP("aaaaaaaaaaabbbbbbbbbbbbbbbbbbbaaaaaaaaaaa", "aaaaaaaabbbbbbbb", 0);
	printf("%d", ret);
	return 0;
}

參考文獻：

1.《大話資料結構》程杰清華大學出版社

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/304983.html

標籤：其他

上一篇：（十）ajax異步重繪問題（input和button）

下一篇：CAD快捷鍵大全

一次性搞懂KMP演算法，解決你對k=next[k]的回溯疑惑

一次性搞懂KMP演算法

如果你是想來看為什么k=next[k],可以翻到第二章的情況2去看；如果你是和我一樣的萌新小白想了解KMP演算法，可以從頭讀起，了解KMP演算法的動機和具體實作原理最后了解其C語言實作細節，

一、動機

二、next陣列

三、C語言實作

2.1 KMP函式

2.2 Getnext函式

四、改進的KMP演算法