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位