之前在數(shù)據(jù)結(jié)構(gòu)書上面看過KMP算法的介紹，但是一直沒有弄懂。發(fā)現(xiàn)胡凡的《算法筆記》對(duì)該算法的描述非常透徹，因此記錄下(ps:下面的圖片來自于該書)

next數(shù)組

在正式進(jìn)入KMP算法之前，先來學(xué)習(xí)一個(gè)重要的數(shù)組。假設(shè)有一個(gè)字符串s(下標(biāo)從0開始)，那么它以i結(jié)尾的子串就是s[0..i]，對(duì)于該子串來說，長(zhǎng)度為k+1的前綴和后綴分別是s[0..k]和s[i-k..i]，現(xiàn)在定義一個(gè)數(shù)組next(請(qǐng)先不要在意名字)，其中next [i]表示使子串s[0..i]的前綴s[0..k]等于后綴s[i-k...i]的最大k(注意前綴和后綴可以重疊，但不能是s[0..i]本身)；如果找不到相同的前后綴，就令next[i]=-1。換句話說，next[i]就是所求最長(zhǎng)相等前后綴中前綴的最后一位的下標(biāo) (ps:這句話非常重要！)

以字符串s="ababaab"為例，next數(shù)組的計(jì)算過程如下所示，圖中給出了上框和下框是等價(jià)的表示，其中上框的前后綴用下劃線表示出了，而下框把后綴和前綴用2行來分開表示。建議先看上框再看下框，會(huì)有不一樣的體驗(yàn)喔。

(1) i=0，子串s[0..i]為“a”，前后綴不能是子串本身，因此令next[0]=-1

(2)i=1，子串s[0..i]為“ab”，由于找不到相等的前后綴，因此令next[0]=-1

(3)i=2，子串s[0..i]為“aba”，能使前后綴相等的最大的k等于0，此時(shí)前綴s[0..k]="a"，后綴s[i-k,i]="a"，而當(dāng)k=1時(shí)，前綴s[0..k]="ab"，后綴s[i-k,i]="ba"，它們不相等，因此next[2]=0

(4)i=3，子串s[0..i]為“abab”，能使前后綴相等的最大的k等于1，此時(shí)前綴s[0..k]="ab"，后綴s[i-k,i]="ab"，而當(dāng)k=2時(shí)，前綴s[0..k]="aba"，后綴s[i-k,i]="bab"，它們不相等，因此next[3]=1

(5)i=4，子串s[0..i]為“ababa”，能使前后綴相等的最大的k等于2，此時(shí)前綴s[0..k]="aba"，后綴s[i-k,i]="aba"，而當(dāng)k=3時(shí)，前綴s[0..k]="abab"，后綴s[i-k,i]="baba"，它們不相等，因此next[4]=2。

(6)i=5，子串s[0..i]為“ababaa”，能使前后綴相等的最大的k等于0，此時(shí)前綴s[0..k]="a"，后綴s[i-k,i]="a"，而當(dāng)k=1時(shí)，前綴s[0..k]="ab"，后綴s[i-k,i]="aa"，它們不相等，因此next[5]=0。

(7)i=6，子串s[0..i]為“ababaab”，能使前后綴相等的最大的k等于1，此時(shí)前綴s[0..k]="ab"，后綴s[i-k,i]="ab"，而當(dāng)k=2時(shí)，前綴s[0..k]="aba"，后綴s[i-k,i]="aab"，它們不相等，因此next[6]=1。

再次強(qiáng)調(diào)：next[i]就是子串s[0..i]的最長(zhǎng)相等前后綴中前綴的最后一位的下標(biāo)。

現(xiàn)在的問題是如何來求解next數(shù)組？假設(shè)已經(jīng)求得了next[0]=-1、next[1]=-1、next[2]=0、next[3]=1，現(xiàn)在來求解next[4]。參看下面的圖，next[3]=1時(shí)，最長(zhǎng)相等的前后綴為“ab”，之后再計(jì)算next[4]時(shí)，由于s[4]==s[next[3]+1]，因此可以把最長(zhǎng)相等前后綴擴(kuò)展為“aba”，而此時(shí)next[4]=next[3]+1=2，并讓j指向next[4] (j的作用在代碼中體現(xiàn))。

接著在求next[5]，但是由于s[5]!=s[next[4]+1]，因此無法擴(kuò)展最長(zhǎng)相等前后綴，即無法通next[4]+1的方法獲得next[5]。這個(gè)時(shí)候怎么辦呢？既然前后綴沒有辦法達(dá)到那么長(zhǎng)，那么不妨縮短一點(diǎn)！此時(shí)希望找到一個(gè)j,使得s[5]=s[j+1]成立并且s[0..j](下圖中的波浪線～)是s[0..2]=“aba”的后綴(s[0..j]顯然是s[0..2]的前綴)。同時(shí)為了讓找的的相等前后綴盡可能長(zhǎng)，找到的j應(yīng)該盡可能大。

是否想到什么了？實(shí)際上要求圖中波浪線的部分(即s[0..j])既是s[0..2]的前綴又是s[0..2]的后綴，同時(shí)希望其長(zhǎng)度盡可能長(zhǎng)。是的，s[0..j]就是s[0..2]的最長(zhǎng)相等前后綴。也就是說，只有令j=next[2]，然后判斷s[5]==s[j+1]是否成立。如果成立，說明s[0..j+1]是s[0..5]的最長(zhǎng)相等前后綴，令next[5]=j+1即可；如果不成立，就不斷讓j=next[j]，直到j(luò)回退到-1，或中途s[5]==s[j+1]成立。如下   圖j從2回退到next[2]=0，發(fā)現(xiàn)s[5]==s[j+1]不成立，就繼續(xù)讓j從0回退到next[0]=-1；由于j已經(jīng)回退到-1，因此不再繼續(xù)回退。這時(shí)驚喜地發(fā)現(xiàn)s[i]==s[j+1]，說明s[0..j+1]是s[0..5]的最長(zhǎng)相等前后綴，于是令next[5]=j+1=-1+1=0。

下面總結(jié)next數(shù)組的求解過程，并給出代碼，讀者可以結(jié)合上面的例子理解：

(1)初始化數(shù)組next，令j=next[0]=-1

(2)讓i在1~len-1范圍內(nèi)遍歷，對(duì)每個(gè)i，執(zhí)行(3)(4)，以求解next[i]

(3)不斷令j=next[j]，直到j(luò)回退到-1，或是s[i]==s[j+1]成立。

(4)如果s[i]==s[j+1]，則next[j]=j+1;否則next[i]=j

void getNext(string s){	int i,j;	j=next[0]=-1;//初始化數(shù)據(jù)next 	for(i=1;s[i];i++){		while(j!=-1 && s[i]!=s[j+1]){			j=next[j];		}		if(s[i]==s[j+1]){			j++;		}		next[i]=j;	}}
KMP
在此前的基礎(chǔ)上，正式進(jìn)入KMP算法的學(xué)習(xí)。你會(huì)發(fā)現(xiàn)，有了上面的基礎(chǔ)，KMP就是在依樣畫葫蘆。此處給出一個(gè)文本字符串text和一個(gè)模式串pattern,然后判斷pattern是否是文本字符串text的子串。以text="abababaabc" 、pattern="ababaab"為例。令i指向text的當(dāng)前欲比較位，令j指向pattern中當(dāng)前已被匹配的最后位，這樣只要text[i]==pattern[j+1]就說明pattern[j+1]也被成功匹配，此時(shí)繼續(xù)讓i、j加1比較，直到j(luò)到達(dá)m-1時(shí)說明pattern是text的子串 。如下圖所示，i=4之前都成功匹配了。此時(shí)i指向text[5]、j指向pattern[4]，標(biāo)明pattern[0..4]已被成功匹配。于是嘗試判斷text[i]==pattern[j+1]是否成立，如果成立，則pattern[0..5]被匹配成功，可令i、j加1繼續(xù)匹配下一位，但十分不幸，此處text[5]!=pattern[4+1]，匹配失敗。似乎很讓人懊惱，難道要放棄之前的pattern[0..4]的成功匹配結(jié)果，讓j回退到-1重新匹配嗎？當(dāng)然不是，只有暴力的做法才那么做！
那么該怎么做呢？為了不讓j直接回退到-1，應(yīng)該尋求回退到一個(gè)離當(dāng)前j最近的位置j'，使得text[i]=pattern[j'+1]能夠成立，并且pattern[0..j']仍然與text的相應(yīng)位置處于匹配狀態(tài)，即pattern[0..j']是pattern[0...j]的相同前后綴。這很容易令人聯(lián)想到之前求next數(shù)組的類似問題。答案是pattern[0..j']是pattern[0...j]的最長(zhǎng)相等前后綴。也就是說，只有不斷令j=next[j]，直到j(luò)回退到-1或者text[i]==pattern[j+1]成立，然后繼續(xù)匹配。從這個(gè)角度講，next數(shù)組的含義就是當(dāng)j+1位失配是，j應(yīng)該回退的位置！
下面總結(jié)KMP算法的一般思路：
(1)初始化next數(shù)組和j=-1,表示pattern當(dāng)前已經(jīng)被匹配的最后一位
(2)讓i遍歷文本text，對(duì)每個(gè)i，執(zhí)行(3)(4)來試圖匹配text[i]和pattern[j+1]
(3)不斷令j=next[j]，直到j(luò)回退到-1，或是text[i]==pattern[j+1]成立。
(4)如果text[i]==pattern[j+1]，則j++。如果j到底m-1，說明pattern是text的子串，返回true。
bool KMP(string text,string pattern){	getNext(pattern); //計(jì)算pattern的next數(shù)組	int j=-1;	int p_len=pattern.length();	for(int i=0;text[i];i++){		while(j!=-1 && text[i]!=pattern[j+1]){			j=next[j];		}		if(text[i]==pattern[j+1]){			j++;		}		if(j==p_len-1){//匹配成功			return true;		}	}	return false;}
接著如果要統(tǒng)計(jì)pattern在text中出現(xiàn)了多少次，只有在j==p_len-1的時(shí)候進(jìn)行累計(jì)即可，但問題在于，這之后應(yīng)該從模式串的哪個(gè)位置開始下一次匹配。通過上面的分析，可以聯(lián)想到next[j]，因?yàn)榇藭r(shí)的next[j]代表整個(gè)模式串pattern的最長(zhǎng)相等前后綴，從這個(gè)位置可以讓j最大，即讓已經(jīng)匹配的部分最長(zhǎng)，這樣既保證不漏解，又是下一次的匹配省去了許多沒有意義的比較。
if(j==p_len-1){//匹配成功	count++;	j=next[j]}