一文帶你入木三分地理解字串KMP演演算法以及C++實現

1. KMP演演算法簡介

溫馨提示:在通篇閱讀完並理解後再看簡介效果更佳以下簡介由百度百科提供

KMP演演算法是一種改進的字串匹配演演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP演演算法）。KMP演演算法的核心是利用匹配失敗後的資訊，儘量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是通過一個next()函數實現，函數本身包含了模式串的區域性匹配資訊。KMP演演算法的時間複雜度O(m+n)

2. 對演演算法本質的理解

注意：為了敘述方便，本小節中的索引都從1開始而非0

抽象理解人眼是如何匹配字串的

我們要在字串1中查詢字串2，則把字串1稱為文字串，字串2成為匹配串。

人眼在文字串與匹配串中來回掃描，一個個判斷兩串字元是否相等(你可能覺得你能一下子比較五個以上字元，但不妨理解為你的大腦還是一個個比較的)。如下圖所示：當人眼發現兩個字元不相等時，視線(圖中紅色區塊)不會移到兩串的起始位置重新比較，而是會找到文字串視線曾經過區域中與匹配串某字首(圖中黃色區塊)相等的地方開始比較，

當我們對匹配字串時人視線的移動進行模擬便可以實現KMP這一高效的匹配演演算法。

用最大公共前字尾與指標模擬人眼操作

我們如此定義最大公共前字尾：在匹配串位置[1，N]的區塊中找一個子串，使得該子串既是最長的字首，又是最長的字尾，並且該子串不能等於該區塊本身,則稱該子串為匹配串位置[1，N]的區塊的最大公共前字尾。

例如下圖：

對於匹配串AAXAAXAA，可以發現AAXAA就是它的最大公共前字尾。

需要用到最大公共前字尾做什麼呢？別急，咱們根據以下幾個步驟循序漸進地理解：

1.假設匹配串與文字串在位置[1，W-1]都相等，在位置W字元不等，在此條件下我們設pre為[1，W-1]區域中匹配串的某字首(下文會確定下來)，設指標i指向文字串中的字元，指標j指向匹配串中的字元。

模擬人眼的操作，此時我們要在文字串[1,W-1]之間(去除已經和pre比較過的部分)尋找pre並由此移動指標。

2.由於是從前向後匹配字串的，所以如果pre在[1,W-1]這個文字串區塊間存在，其第一次出現一定是出現在區塊的末尾，也就是說它就是區塊的字尾。又由於匹配串與文字串在位置[1,W-1] 都相等，所以pre也是匹配串的字尾，於是成為了匹配串[1，W-1]區域的公共前字尾。

圖例：

3.我們這時候就可以嘗試著使用公共前字尾將比較字串的視線移動用指標具象化。當雙指標所指的字元相同時，令i++；j++即可；若字元不同時，我們如此考慮：

• 當文字串[1，W-1] (去除已經和pre比較過的部分)中含有pre，即在[1，W-1] 有公共前字尾(pre長大於0)時。我們記len[W-1]為匹配串的字首終止位置，從上文得文字串字尾的終止位置為W-1，由於匹配串的字首與文字串的字尾相對應，所以我們只需要從匹配串字首與文字串字尾之後開始比較即可。即令i不變仍為W；j=len[W-1]+1。
• 我們又額外考慮當文字串[1，W-1] (去除已經和pre比較過的部分)中不含pre，即在[1，W-1] 無公共前字尾(pre長為0)時的情況。這時完全可以看作len[W-1]=0，與上一種情況一致，i不變保持W；j=len[W-1]+1。

指標移動圖例：

所以無論哪種情況，文字串上的指標i不會回退，而匹配串的指標j則會根據不同情況而回退

4.到這公共前字尾的價值已經很明確了，只要找出每一個[1，W-1]區域匹配串的公共前字尾之長len[W-1]，那麼就可以得到如下指標移動公式，使得每次字元不同時，指標的移動模擬了人眼的匹配過程。

5.這裡我們應當確立步驟1中的某字首應當為滿足匹配串[1，W-1]區域的公共前字尾最大時的字首。也就是說要pre滿足其為匹配串[1，W-1]區域的最大公共前字尾。理由：見下圖兩個取不同大小公共前字尾的範例的比較次數，其中橙色區塊為公共前字尾，藍色區塊為指標j回退後還需要比較的字元，明顯取大的公共前字尾的比較字元更少(因為大的公共前字尾中包括了小的公共前字尾情況下還需要比較的字元)。

以AA為公共前字尾時：還需比較7個字元

以AAXAA為公共前字尾時：還需比較4個字元

歸納：到這裡為止，我們所有的問題就轉化為了求len[W-1]，即求匹配串[1，W-1]中最大公共前字尾的值。

3. 使用next陣列求解最大公共前字尾長度

注意：上文說到，我們只要知道len[W-1]的值，便可以在位置W處字元不等式快速找到指標回退的位置。然而在大多數官方的解釋中，這個len陣列被命名為next，為了規範化，我們下文中會用next陣列來稱呼len陣列。此外，索引仍從1開始。

我們設字串F表示匹配串，設next[index]表示匹配串[1，index]區域中最大公共前字尾的長度。並使用使用雙指標求解，指標i指向當前字元位置(也可以看作就是字尾終止位置)，用指標j指向[1，i]間最大公共前字尾的字首終止位置(同時可以發現j就是最大公共前字尾長度)，
求最大公共前字尾的過程如下，當i從1向匹配串末尾遍歷時

• 若F[j+1]=F[i],說明當下字首之後的第一個位置與字尾終止字元相等，那麼最大公共前字尾就可以增加一個字元，字首終止位置可以指向下一個字元，即next[i]=j+1；j++。
• 若F[j+1]≠F[i]，此時的情況就需要分多步進行理解：

1.可以把當前的狀態用下圖表示，其中整個矩形為匹配串[1，i]的部分，可見A=F[j+1]，B=F[i]。

2.現在我們先將問題轉化為以下這種情況，找到一個如下的橙色部分，判斷A是否與C相等，相等則橙色部位加上F[i]即為[1，i]的最大公共前字尾。

所以我們可以確定橙色部分長度為next[j]。

3.將上圖簡化為下圖，我們發現這個狀態是似曾相識的

我們不如直接令j回退到next[j]處，然後再判斷F[j+1]與F[i]是否相等，這時一切又轉化為整個過程的開始。

4.可以發現，當F[j+1]≠F[i]時，我們總是周而復始找到j這個最大公共前字尾的最大公共前字尾，然後重新判斷，直到無最大公共前字尾或者判斷出相等。

歸納：至此我們已經可以對於任意索引index,求出匹配串[1，index]區間的最大公共前字尾長度，結合上部分指標移動公式即可完成KMP演演算法。

4. 用c++程式碼實現

#include<bits/stdc++.h>
using namespace std;
//索引仍然從1開始 
void getNext(int* next,string key){
	//輸入空next陣列與匹配串key，將next陣列生成為key的最大公共前字尾陣列
      int j=0;next[1]=0;
      for(int i=2;i<key.length();i++){
      	while(j>0 && key[i]!=key[j+1]) j=next[j];//不斷尋找最大公共前字尾的最大公共字首，直到最大公共前字尾或者判斷出相等。
		if(key[i]==key[j+1]) j++;//判斷出相等，最大公共前字尾增長
		next[i]=j;
	  }
}
int KMP(string text,string key){
	/*輸入文字串與匹配串，返回匹配串在文字串中的位置
	找不到則返回-1*/ 
	text=" "+text;key=" "+key;//因為索引從1開始，所以要在0的位置墊上空格 
    if(key.length() == 0)return -1;
    int next[key.length()+1];
    getNext(next, key);//生成匹配串的next陣列 
    int j=1,i=1;
    while(j < key.length() && i < text.length()){
    	if(text[i] == key[j])i++,j++;//當字元相等時的公式 
		else j = next[i-1]+1;//當字元不等時的公式 
	}
	if(j == key.length())return i-key.length()+1;
    return -1;
}
int main() {
	string text,key;//文字串與匹配串
	cin>>text>>key;
    int i=KMP(text,key);
    printf("匹配串出現在文字串第%d位",i);
    return 0;
}

輸入：AAXAAXAAXAAD AAXAAXAAD

輸出：匹配串出現在文字串第4位元

以上就是一文帶你入木三分地理解字串KMP演演算法以及C++實現的詳細內容，更多關於C++ KMP演演算法的資料請關注it145.com其它相關文章！