• 前言
• 一、串
• • 1.串的定義
  • 2.串的一些概念
  • • ①空格串
    • ②空串
    • ③子串與主串
  • 3.串的抽象數(shù)據(jù)類型
• 二、例題
• 三、模式匹配算法
• • 1.暴力匹配算法
  • 2.關(guān)于暴力匹配的思考
  • 3.KMP模式匹配算法
  • • ①KMP的由來
    • ②KMP的用處
    • ③KMP算法的引入
    • ④前綴表
    • ⑤最長公共前后綴
    • ⑥使用前綴表的原因
    • ⑦前綴表與next數(shù)組
    • ⑧構(gòu)造next數(shù)組
    • ⑨使用next數(shù)組來做匹配
    • ⑩KMP的時間復(fù)雜度
    • ⑩①例題完整KMP算法代碼
• 總結(jié)
• • 總結(jié)1
  • 總結(jié)2
  • 總結(jié)3

最近因提前放假筆者放假，擺了很大一段時間，心里負(fù)罪感十分沉重，因此決定洗心革面，重新做人。從本周開始恢復(fù)每周的周報，拒絕擺爛。

本周將從串開始引入，重點(diǎn)介紹有關(guān)串的KMP算法。

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

串是由零個或多個字符組成的有限序列，又名叫字符串

在我們先前的學(xué)習(xí)中，我們對串實(shí)質(zhì)上已經(jīng)十分了解，本文對此不再贅述。我們重點(diǎn)介紹一些概念

只包含空格的串，要注意它與空串的區(qū)別，空格串是由內(nèi)容與長度的。而且可以不止一個空格。
這里注意一個串中也是可以包含多個空格的，例如：

I like CaiXukun

零個字符的串稱為空串

串中任意個數(shù)的連續(xù)字符組成的子序列稱為該串的子串，相應(yīng)地，包含子串的串稱為主串。
子串在主串中的位置就是子串的第一個字符在主串中的符號
例如Xukun便是CaiXukun的子串

串的邏輯結(jié)構(gòu)與線性表很相似，不同之處在于串針對的是字符集，也就是串中的元素都是字符。

因此，對于串中的基本操作和線性表是有很大差別的。線性表更關(guān)注的是單個元素的操作。 比如查找一個元素，插入或刪除一個元素，但串中更多的是查找子串位置，得到指定位置子串、替換子串等操作。

在下筆者將會貼出一些與串有關(guān)的基本操作。在此不逐一分析，僅供參考。

我們將以以下這一道例題展開我們重點(diǎn)展開我們對于與串有關(guān)的算法的學(xué)習(xí)。

找出字符串中第一個匹配項(xiàng)的下標(biāo)

在我們介紹有關(guān)例題的兩種方法，我們先來介紹有關(guān)串的模式匹配。

串的模式匹配就類似于我們在一篇文章中尋找一個單詞（相當(dāng)于一個大字符串中找所需要的小字符串）的定位問題。這種子串的定位操作通常稱作串的模式匹配。

暴力算法也叫BF算法
在此筆者簡單介紹暴力匹配的基本思想：

就是將主串中的每一個字符都作為子串的開頭，與要匹配的字符串進(jìn)行匹配。
另外這之中的代碼實(shí)現(xiàn)操作便是對主串做大循環(huán)，每個字符開頭做T的長度的小循環(huán)。直到匹配成功或全部遍歷完成為止。

下面筆者給出例題的暴力匹配算法的代碼：

#includeint BF(char *s,char *t)//s為主串，t為模式串 
{int i = 0,j = 0;
	while(s[i]!='\0'&&t[j]!='\0')//兩個串都沒有掃描完時循環(huán) 
	{if(s[i]==t[j])//當(dāng)前兩個字符相同 
		{	i++;j++;//比較后續(xù)字符 
		}
		else//當(dāng)前兩個字符不同 
		{	i=i-j+1;//掃描主串的i回退 
			j=0;//模式串回溯為0，從頭匹配 
		}
	}
	if(t[j]=='\0')//如果j越界，表示模式串遍歷完，t是s的字串 
		return i-j;//返回目標(biāo)串中子串的起始位置 
	else
		return 0;
}
int main()
{char s[5]={'a','c','a','b','a'};
	char t[2]={'a','b'};
	printf("%d",BF(s,t));
}

暴力匹配也許是大多數(shù)人首先能想到的方法。但是他的時間復(fù)雜度過于高了，我們分析一下最好的情況時間復(fù)雜度可能是O(1)，同時最壞的情況便是O(n+m)。

在此，我們要明白字符串暴力匹配的實(shí)質(zhì)：
通過對主串中i值的不斷回溯來實(shí)現(xiàn)

如何理解這句話呢？

因?yàn)楸┝ζヅ渲兄鞔拿恳粋€字母都需要與模板串的首字母匹配依次。那么對于主串的指針i會不斷前進(jìn)，當(dāng)當(dāng)前主串字母與模板串當(dāng)前字母不符合時，那么讓i值回溯當(dāng)前掃描的字母的下一個字母。

例如：
主串：Cai Xuku Xukun （加上空格是為了方便閱讀）
模板串：Xukun

我們使用暴力匹配掃描時，當(dāng)掃描到主串的第四個字母X時，主串與模板串匹配成功，i 與 j 都會向后移動。
直到 i 掃描到第8個字母X時，我們發(fā)現(xiàn)后續(xù)的匹配失敗了，那么i便會回溯到第5個字母u重新開始匹配。

那么這里就成為了我們優(yōu)化算法的關(guān)鍵。我們有沒有一種辦法可以使 i 不去回溯，而是一直前進(jìn)，但仍然實(shí)現(xiàn)我們目的的算法呢？
由此我們的KMP算法出現(xiàn)了。

我們在后續(xù)將會學(xué)到許多算法，為避免大家混淆，筆者對KMP算法起了一個比較下流中文名——看毛片算法。
此名僅供參考記憶，如有雷同純屬偶然。

說到KMP，先說一下KMP這個名字是怎么來的，為什么叫做KMP呢。

因?yàn)槭怯蛇@三位學(xué)者發(fā)明的：Knuth，Morris和Pratt，所以取了三位學(xué)者名字的首字母。所以叫做KMP

KMP的經(jīng)典思想就是:當(dāng)出現(xiàn)字符串不匹配時，可以記錄一部分之前已經(jīng)匹配的文本內(nèi)容，利用這些信息避免從頭再去做匹配。

我們以此來優(yōu)化算法的時間復(fù)雜度。

為了更好地理解KMP算法，筆者在此先給出KMP算法的實(shí)現(xiàn)步驟。。當(dāng)你看到以下內(nèi)容時你可能會覺得摸不著頭腦，這是很正常的。但是希望你能堅持看完，筆者在下文會一步步講解每一步做法的原因。

假設(shè)現(xiàn)在文本串S匹配到 i 位置，模式串P匹配到 j 位置 如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++，繼續(xù)匹配下一個字符； 如果j != -1，且當(dāng)前字符匹配失?。碨[i] != P[j]），則令 i
不變，j = next[j]。此舉意味著失配時，模式串P相對于文本串S向右移動了j - next [j] 位。
換言之，當(dāng)匹配失敗時，模式串向右移動的位數(shù)為：失配字符所在位置 - 失配字符對應(yīng)的next 值（next 數(shù)組的求解會在下文的3.3.3節(jié)中詳細(xì)闡述），即移動的實(shí)際位數(shù)為：j - next[j]，且此值大于等于1。

細(xì)心的你在這里一定會發(fā)現(xiàn)在筆者引用的描述中出現(xiàn)了一個從來沒見過的next數(shù)組。那么這個next數(shù)組就是我們實(shí)現(xiàn)KMP的關(guān)鍵。

在這里我們回憶一下我們用KMP算法是如何通過優(yōu)化取代BF算法的：
通過避免出現(xiàn)不必要的回溯來優(yōu)化算法的復(fù)雜度

在BF算法中，i 與 j 的值都會不斷回溯，但是對于KMP算法，我們不對 i 的值進(jìn)行回溯。那么出現(xiàn)變化的只有 j 了。（這里需要著重理解一下）

在KMP算法中，j 值的變化其實(shí)與主串（文本串）并無關(guān)系，j值的多少取決模板串中的結(jié)構(gòu)是否由重復(fù)的問題。

在解釋KMP算法中的next數(shù)組前，我們必須引入一個概念：前綴表。

那么什么是前綴表：記錄下標(biāo)i之前（包括i）的字符串中，有多大長度的相同前綴后綴。

next數(shù)組就是一個前綴表（prefix table）。

前綴表有什么作用呢？

前綴表是用來回退的，它記錄了模式串與主串(文本串)不匹配的時候，模式串應(yīng)該從哪里開始重新匹配。

為了更好地解釋前綴表，我們在這里舉一個例子：

要在文本串：aabaabaafa 中查找是否出現(xiàn)過一個模式串：aabaaf。

這里我們一定要懂得文本串與模式串的區(qū)別，我們把文本串看作一篇文章，那么模式串就是這篇文章中出現(xiàn)的單詞。

我們可以發(fā)現(xiàn)文本串中第六個字符b 和 模式串的第六個字符f，不匹配了。如果暴力匹配，發(fā)現(xiàn)不匹配，此時就要從頭匹配了。

但如果使用前綴表，就不會從頭匹配，而是從上次已經(jīng)匹配的內(nèi)容開始匹配，找到了模式串中第三個字符b繼續(xù)開始匹配。

我們在前綴表中定義中出現(xiàn)了相同前后綴這個名詞，我們在以下對此展開討論。
對于這個名詞我們需要將其拆分成最長，前綴，后綴三個詞來分別理解。

前綴是指不包含最后一個字符的所有以第一個字符開頭的連續(xù)子串。
后綴是指不包含第一個字符的所有以最后一個字符結(jié)尾的連續(xù)子串。

例如：aabaa， aab可以說是這一個字符串的一個前綴，baa是這一個字符串的一個后綴。

有的博主將公共修改為相等，我認(rèn)為這是大同小異的，只是每個人對于同一個詞的理解不同。

例如：字符串a(chǎn)的最長公共前后綴為0。 字符串a(chǎn)a的最長公共前后綴為1。 字符串a(chǎn)aa的最長公共前后綴為2。 等等…

在這里筆者通過aaa的最長公共前后綴為2來展開討論。我們在上文已經(jīng)提到：
前綴是指不包含最后一個字符的所有以第一個字符開頭的連續(xù)子串。
后綴是指不包含第一個字符的所有以最后一個字符結(jié)尾的連續(xù)子串。
那么aaa的最長后綴便是aa，最長前綴也是aa。

在這里我們便可以通過我們上文對于前綴表的定義：記錄下標(biāo)i之前（包括i）的字符串中，有多大長度的相同前綴后綴。 從而求得前綴表的值了。

我們在上文知道了前綴表可以用來告訴我們當(dāng)匹配失敗時要回退的下一個位置。這是我們已經(jīng)明白的結(jié)果。但是究其原因，我們?yōu)槭裁葱枰@樣做呢，為什么這樣做就可以避免 i 的回溯從而減少時間復(fù)雜度呢？在這里筆者將給出自己粗略的見解，如有錯誤，請不吝指出。

在這里，筆者通過給出求前綴表的代碼加以解釋

在看代碼之前請筆者將給出代碼中各個變量的含義：
j 指向前綴的末尾位置， 同時也代表i之前的串的最長公共前后綴長度
而 i 指向后綴的開頭位置

void Getnext(char* P, int* next)
{int j = 0;
	next[0] = j;
	int len = strlen(P);
	for (int i = 1; i< len; ++i)
	{while (j >0 && P[i] != P[j])
		{	j = next[j - 1];//自我匹配遞歸，要好好理解
		}
		if (P[i] == P[j])
			j++;
		next[i] = j;
	}
}

在此處需要聲明一點(diǎn)，那就是next數(shù)組是通過前綴表的變化而得到的，next數(shù)組有多種變化方法，但始終離不開前綴表，也就是說next數(shù)組的不同只是表達(dá)方式不一樣，并不會影響前綴表，因此用前綴表原型來表達(dá)next數(shù)組也是成立的。

我們以下面這張圖片來講解筆者上述代碼中注釋的自我匹配遞歸的意思，這里是筆者認(rèn)為的比較難以理解的地方。

一、我們已知此時 i 指針已經(jīng)移動到模式串中的 f 的位置， j 移動到了模式串中的 b 的位置。
(讀者可自行根據(jù)上述代碼推導(dǎo)，筆者這里重點(diǎn)在于幫助讀者理解前綴表是如何作用的） 二、那么根據(jù)我們的代碼我們的 f 與 b
進(jìn)行匹配，發(fā)現(xiàn)了匹配失敗， 那么通過代碼 j = next[j-1]， 我們知道 j 需要回退到下標(biāo)為1的a的位置，
此時下標(biāo)為1的a的最長公共前綴和為1，那么 a 再次與 f 重新匹配， 依然匹配失敗，那么繼續(xù)回退， 直至 j = 0。

另外，許多博主在此講述的方法是通過遞歸理解，筆者在此給出一種用對稱性理解的思路，之所以可以使用這種思路是因?yàn)閚ext數(shù)組中的前綴與后綴的長度相同。

我們同樣使用 f 進(jìn)行舉例，此時如果 f 與 b 配對成功， 那么 f 位置的最長公共前后綴是3，但很顯然是失敗的。
同時我們需要記住一點(diǎn)那就是前綴的長度與后綴相同。那么我們就需要退而求其次，我們需要去探究當(dāng)最長公共前后綴是2時是否成立，(在這里其實(shí)就是45位置的af又與01位置的aa匹配,只不過因?yàn)槲覀兺ㄟ^前面的過程已經(jīng)完成了0下標(biāo)位置的a與4位置的a的匹配，實(shí)際上只需要對1位置的a與5位置的f進(jìn)行匹配)
那么 j 指針就移動到了下標(biāo)為1的 a 的位置與 f 進(jìn)行對比。我們?nèi)绱酥鸩娇s短最長公共前后綴的長度，來探究當(dāng)前位置指針 i 的最長公共前后綴是多少。

在理解這一步驟時筆者也參考了多方的資料，筆者的講解能力也是依托答辯，在如下粘貼兩篇大牛的文章，供讀者學(xué)習(xí)與參考（當(dāng)然如若能夠理解筆者的稀碎文筆筆者不盡感激）
從頭到尾徹底理解KMP（2014年8月22日版）
代碼隨想錄kmp 28. 實(shí)現(xiàn) strStr()

我們在前文用了大量的篇章描述前綴表，就是為了引出此刻的next數(shù)組。若是您對上文有仔細(xì)地閱讀，會發(fā)現(xiàn)其實(shí)在上文我們已經(jīng)使用了next數(shù)組。

next數(shù)組就可以是前綴表，但是很多實(shí)現(xiàn)都是把前綴表統(tǒng)一減一（右移一位，初始位置為-1）之后作為next數(shù)組。
其實(shí)這并不涉及到KMP的原理，而是具體實(shí)現(xiàn)，next數(shù)組既可以就是前綴表，也可以是前綴表統(tǒng)一減一（右移一位，初始位置為-1）。

注意：這里的-1與右移的操作，其實(shí)都是為了方便代碼的實(shí)現(xiàn)而設(shè)計出來的，如果有興趣的讀者可以自行了解，筆者在此處僅講述不通過變化直接應(yīng)用前綴表的next數(shù)組的用法。

在我們構(gòu)造next數(shù)組之前，筆者在此給出next數(shù)組的偽代碼，依次來展開我們對于next數(shù)組代碼的實(shí)現(xiàn)

void Getnext(char* P, int* next)
{初始化;
	處理前后綴不相同的情況;
	前后綴相同;
	更新;
}

聲明代碼中的變量: j 指向前綴的末尾位置， 同時也代表i之前的串的最長公共前后綴長度 而 i 指向后綴的開頭位置

1、初始化：

int j = 0;//因?yàn)閖指向前綴的末尾位置， 前綴最開始在0的位置
next[0] = 0;//前綴表剛開始時只有一個字母，既無前綴也無后綴

因?yàn)閖指向前綴的末尾位置， 前綴最開始在0的位置
前綴表剛開始時只有一個字母，既無前綴也無后綴

2、處理前后綴不相同的情況：

for(int i =1; i

i 作為后綴的開頭從1下標(biāo)的位置開始于j進(jìn)行匹配

如果匹配失敗

while (j >0 && P[i] != P[j])
		{	j = next[j - 1];//自我匹配遞歸，要好好理解
		}

此時這種情況其實(shí)就是前后綴不相同，那么就需要向前回退

3、處理前后綴相同的情況

if (P[i] == P[j])
			j++;
		next[i] = j;

匹配成功，那么 i 與 j 都會加1。

for (int i = 0; i< S_len; ++i)

while (j >0 && S[i] != P[j])
		{	j = next[j - 1];
		}

if (S[i] == P[j])
		{	j++;
		}

if (j == P_len)
		{	printf("%d\n", (i - len2 + 1));//輸出成功的文本串中的首位置
			return 0;
		}

void Getnext(char* P, int* next)
{int j = 0;
	next[0] = j;
	int len = strlen(P);
	for (int i = 1; i< len; ++i)
	{while (j >0 && P[i] != P[j])
		{	j = next[j - 1];//自我匹配遞歸，要好好理解
		}
		if (P[i] == P[j])
			j++;
		next[i] = j;
	}
}


int main()
{char S[100];
	char P[100];
	gets_s(S);
	gets_s(P);
	int len1 = strlen(S);
	int len2 = strlen(P);
	int* next = (int*)malloc(sizeof(int) * len2);
	Getnext(P, next);
	if (len2 == 0) {return 0;
	}
	int j = 0;
	for (int i = 0; i< len1; ++i)
	{while (j >0 && S[i] != P[j])
		{	j = next[j - 1];
		}
		if (S[i] == P[j])
		{	j++;
		}
		if (j == len2)
		{	printf("%d\n", (i - len2 + 1));
			return 0;
		}
	}
	printf("-1");

	return 0;
}