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ū)塊)不會移到兩串的起始位置重新比較，而是會找到文本串視線曾經(jīng)過區(qū)域中與匹配串某前綴(圖中黃色區(qū)塊)相等的地方開始比較，

當(dāng)我們對匹配字符串時(shí)人視線的移動進(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ū)域中匹配串的某前綴(下文會確定下來)，設(shè)指針i指向文本串中的字符，指針j指向匹配串中的字符。

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

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)雙指針?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。

指針移動圖例：

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

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

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ī)范化，我們下文中會用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)是似曾相識的

我們不如直接令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é)合上部分指針移動公式即可完成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)文章！

最新評論