1. KMP算法簡介

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

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP算法）。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)就是通過一個(gè)next()函數(shù)實(shí)現(xiàn)，函數(shù)本身包含了模式串的局部匹配信息。KMP算法的時(shí)間復(fù)雜度O(m+n)

2. 對算法本質(zhì)的理解

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

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

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

人眼在文本串與匹配串中來回掃描，一個(gè)個(gè)判斷兩串字符是否相等(你可能覺得你能一下子比較五個(gè)以上字符，但不妨理解為你的大腦還是一個(gè)個(gè)比較的)。如下圖所示：當(dāng)人眼發(fā)現(xiàn)兩個(gè)字符不相等時(shí)，視線(圖中紅色區(qū)塊)不會(huì)移到兩串的起始位置重新比較，而是會(huì)找到文本串視線曾經(jīng)過區(qū)域中與匹配串某前綴(圖中黃色區(qū)塊)相等的地方開始比較，

當(dāng)我們對匹配字符串時(shí)人視線的移動(dòng)進(jìn)行模擬便可以實(shí)現(xiàn)KMP這一高效的匹配算法。

用最大公共前后綴與指針模擬人眼操作

我們?nèi)绱硕x最大公共前后綴：在匹配串位置[1，N]的區(qū)塊中找一個(gè)子串，使得該子串既是最長的前綴，又是最長的后綴，并且該子串不能等于該區(qū)塊本身,則稱該子串為匹配串位置[1，N]的區(qū)塊的最大公共前后綴。

例如下圖：

對于匹配串AAXAAXAA，可以發(fā)現(xiàn)AAXAA就是它的最大公共前后綴。

需要用到最大公共前后綴做什么呢？別急，咱們根據(jù)以下幾個(gè)步驟循序漸進(jìn)地理解：

1.假設(shè)匹配串與文本串在位置[1，W-1]都相等，在位置W字符不等，在此條件下我們設(shè)pre為[1，W-1]區(qū)域中匹配串的某前綴(下文會(huì)確定下來)，設(shè)指針i指向文本串中的字符，指針j指向匹配串中的字符。

模擬人眼的操作，此時(shí)我們要在文本串[1,W-1]之間(去除已經(jīng)和pre比較過的部分)尋找pre并由此移動(dòng)指針。

2.由于是從前向后匹配字符串的，所以如果pre在[1,W-1]這個(gè)文本串區(qū)塊間存在，其第一次出現(xiàn)一定是出現(xiàn)在區(qū)塊的末尾，也就是說它就是區(qū)塊的后綴。又由于匹配串與文本串在位置[1,W-1] 都相等，所以pre也是匹配串的后綴，于是成為了匹配串[1，W-1]區(qū)域的公共前后綴。

圖例：

3.我們這時(shí)候就可以嘗試著使用公共前后綴將比較字符串的視線移動(dòng)用指針具象化。當(dāng)雙指針?biāo)傅淖址嗤瑫r(shí)，令i++；j++即可；若字符不同時(shí)，我們?nèi)绱丝紤]：

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

指針移動(dòng)圖例：

所以無論哪種情況，文本串上的指針i不會(huì)回退，而匹配串的指針j則會(huì)根據(jù)不同情況而回退

4.到這公共前后綴的價(jià)值已經(jīng)很明確了，只要找出每一個(gè)[1，W-1]區(qū)域匹配串的公共前后綴之長len[W-1]，那么就可以得到如下指針移動(dòng)公式，使得每次字符不同時(shí)，指針的移動(dòng)模擬了人眼的匹配過程。

5.這里我們應(yīng)當(dāng)確立步驟1中的某前綴應(yīng)當(dāng)為滿足匹配串[1，W-1]區(qū)域的公共前后綴最大時(shí)的前綴。也就是說要pre滿足其為匹配串[1，W-1]區(qū)域的最大公共前后綴。理由：見下圖兩個(gè)取不同大小公共前后綴的示例的比較次數(shù)，其中橙色區(qū)塊為公共前后綴，藍(lán)色區(qū)塊為指針j回退后還需要比較的字符，明顯取大的公共前后綴的比較字符更少(因?yàn)榇蟮墓睬昂缶Y中包括了小的公共前后綴情況下還需要比較的字符)。

以AA為公共前后綴時(shí)：還需比較7個(gè)字符

以AAXAA為公共前后綴時(shí)：還需比較4個(gè)字符

歸納：到這里為止，我們所有的問題就轉(zhuǎn)化為了求len[W-1]，即求匹配串[1，W-1]中最大公共前后綴的值。

3. 使用next數(shù)組求解最大公共前后綴長度

注意：上文說到，我們只要知道len[W-1]的值，便可以在位置W處字符不等式快速找到指針回退的位置。然而在大多數(shù)官方的解釋中，這個(gè)len數(shù)組被命名為next，為了規(guī)范化，我們下文中會(huì)用next數(shù)組來稱呼len數(shù)組。此外，索引仍從1開始。

我們設(shè)字符串F表示匹配串，設(shè)next[index]表示匹配串[1，index]區(qū)域中最大公共前后綴的長度。并使用使用雙指針求解，指針i指向當(dāng)前字符位置(也可以看作就是后綴終止位置)，用指針j指向[1，i]間最大公共前后綴的前綴終止位置(同時(shí)可以發(fā)現(xiàn)j就是最大公共前后綴長度)，
求最大公共前后綴的過程如下，當(dāng)i從1向匹配串末尾遍歷時(shí)

• 若F[j+1]=F[i],說明當(dāng)下前綴之后的第一個(gè)位置與后綴終止字符相等，那么最大公共前后綴就可以增加一個(gè)字符，前綴終止位置可以指向下一個(gè)字符，即next[i]=j+1；j++。
• 若F[j+1]≠F[i]，此時(shí)的情況就需要分多步進(jìn)行理解：

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

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

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

3.將上圖簡化為下圖，我們發(fā)現(xiàn)這個(gè)狀態(tài)是似曾相識(shí)的

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

4.可以發(fā)現(xiàn)，當(dāng)F[j+1]≠F[i]時(shí)，我們總是周而復(fù)始找到j(luò)這個(gè)最大公共前后綴的最大公共前后綴，然后重新判斷，直到無最大公共前后綴或者判斷出相等。

歸納：至此我們已經(jīng)可以對于任意索引index,求出匹配串[1，index]區(qū)間的最大公共前后綴長度，結(jié)合上部分指針移動(dòng)公式即可完成KMP算法。

4. 用c++代碼實(shí)現(xiàn)

#include<bits/stdc++.h>
using namespace std;
//索引仍然從1開始 
void getNext(int* next,string key){
	//輸入空next數(shù)組與匹配串key，將next數(shù)組生成為key的最大公共前后綴數(shù)組
      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;//因?yàn)樗饕龔?開始，所以要在0的位置墊上空格 
    if(key.length() == 0)return -1;
    int next[key.length()+1];
    getNext(next, key);//生成匹配串的next數(shù)組 
    int j=1,i=1;
    while(j < key.length() && i < text.length()){
    	if(text[i] == key[j])i++,j++;//當(dāng)字符相等時(shí)的公式 
		else j = next[i-1]+1;//當(dāng)字符不等時(shí)的公式 
	}
	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("匹配串出現(xiàn)在文本串第%d位",i);
    return 0;
}

輸入：AAXAAXAAXAAD AAXAAXAAD

輸出：匹配串出現(xiàn)在文本串第4位

以上就是一文帶你入木三分地理解字符串KMP算法以及C++實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++ KMP算法的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論