目錄

?

1.KMP介紹

1.1什么是KMP

1.2KMP有什么用

2.前綴表的介紹

2.1什么是前綴表

2.2前綴表如何記錄

2.3為什么一定要用前綴表

2.4.如何計(jì)算前綴表

3.構(gòu)造next數(shù)組

4.使用next數(shù)組做匹配

5.例題（實(shí)現(xiàn)strStr(Leetcode第28題)）

5.1題目描述

5.2代碼實(shí)現(xiàn)

---

1.KMP介紹

1.1什么是KMP

之所以叫KMP是為了紀(jì)念發(fā)明者，分別為：Knuth，Morris和Pratt

1.2KMP有什么用

KMP主要是應(yīng)用在字符串匹配上。

KMP的主要思想是當(dāng)出現(xiàn)字符串不匹配時(shí)，可以知道一部分之前匹配的文本內(nèi)容，可以利用這些信息避免從頭再去做匹配。

2.前綴表的介紹

2.1什么是前綴表

寫KMP時(shí)用到的next數(shù)組就是前綴表。

前綴表是用來(lái)回溯的，它記錄了模式串與主串（文本串）不匹配的時(shí)候，模式串應(yīng)該從那里重新開(kāi)始匹配。

2.2前綴表如何記錄

首先要知道前綴表的任務(wù)是當(dāng)前位置匹配失敗，找到之前匹配上的位置，再重新匹配，此也意味著在某個(gè)字符失配時(shí)，前綴表會(huì)告訴一下步匹配中字符串應(yīng)跳到那個(gè)位置。

2.3為什么一定要用前綴表

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

在f之前最長(zhǎng)相等的前綴和后綴字符串是子字符串a(chǎn)a，因?yàn)檎业搅俗铋L(zhǎng)相等的前綴和后綴，匹配失敗的位置是后綴子串的后面，那么我們找到與其相同的前綴的后面從新匹配就可以了。所以前綴表具有告訴我們當(dāng)前位置匹配失敗跳到之前已經(jīng)匹配過(guò)得地方的能力。

前綴：包含首字母，不包含尾字母的所有子串。例如：a;aa;aab;aaba;aabaa;

后綴：只包含尾字母不包含首字母的子串。例如：f;af;aaf;baaf;abaaf;

2.4.如何計(jì)算前綴表

長(zhǎng)度為前1個(gè)字符的子串a(chǎn)，最長(zhǎng)相同前后綴的長(zhǎng)度為0。（注意這里計(jì)算相同前后綴，不算重復(fù)的字符）

長(zhǎng)度為前2個(gè)字符的子串a(chǎn)a，最長(zhǎng)相同前后綴的長(zhǎng)度為1。

長(zhǎng)度為前3個(gè)字符的子串a(chǎn)ab，最長(zhǎng)相同前后綴的長(zhǎng)度為0。

以此類推：
長(zhǎng)度為前4個(gè)字符的子串a(chǎn)aba，最長(zhǎng)相同前后綴的長(zhǎng)度為1。
長(zhǎng)度為前5個(gè)字符的子串a(chǎn)abaa，最長(zhǎng)相同前后綴的長(zhǎng)度為2。
長(zhǎng)度為前6個(gè)字符的子串a(chǎn)abaaf，最長(zhǎng)相同前后綴的長(zhǎng)度為0。

那么把求得的最長(zhǎng)相同前后綴的長(zhǎng)度就是對(duì)應(yīng)前綴表的元素，如圖：

可以看出，前綴表里的數(shù)值代表著就是：當(dāng)前位置之前的子串有多大長(zhǎng)度相同的前后綴。

找到的不匹配的位置，那么此時(shí)我們要看它的前一個(gè)字符的前綴表數(shù)值是多少。

為什么要看前一個(gè)字符的前綴表的數(shù)值呢，因?yàn)橐仪懊孀址淖铋L(zhǎng)相同的前綴和后綴，所以要看前一位的前綴表的數(shù)值。

3.構(gòu)造next數(shù)組

我們定義一個(gè)函數(shù)getNext來(lái)構(gòu)建next數(shù)組，函數(shù)參數(shù)為指向next數(shù)組的指針，和一個(gè)字符串。代碼如下：

void getNext(int* next, const string& s)

「構(gòu)造next數(shù)組其實(shí)就是計(jì)算模式串s，前綴表的過(guò)程?！?/strong>?主要有如下三步：

初始化

處理前后綴不相同的情況

處理前后綴相同的情況

接下來(lái)我們?cè)斀庠斀庖幌隆?/p>

初始化：

定義兩個(gè)指針i和j，j指向前綴終止位置（嚴(yán)格來(lái)說(shuō)是終止位置減一的位置），i指向后綴終止位置（與j同理）。然后還要對(duì)next數(shù)組進(jìn)行初始化賦值，如下：

int j = -1; next[0] = j;

j 為什么要初始化為 -1呢，因?yàn)橹罢f(shuō)過(guò) 前綴表要統(tǒng)一減一的操作，所以j初始化為-1。next[i] 表示 i（包括i）之前最長(zhǎng)相等的前后綴長(zhǎng)度（其實(shí)就是j）

所以初始化next[0] = j 。

? ? ?2.處理前后綴不相同的情況

?因?yàn)閖初始化為-1，那么i就從1開(kāi)始，進(jìn)行s[i] 與 s[j+1]的比較。所以遍歷模式串s的循環(huán)下表i 要從 1開(kāi)始，代碼如下：

for(int i = 1; i < s.size(); i++) {

如果 s[i] 與 s[j+1]不相同，也就是遇到 前后綴末尾不相同的情況，就要向前回溯。

怎么回溯呢？

next[j]就是記錄著j（包括j）之前的子串的相同前后綴的長(zhǎng)度。

那么 s[i] 與 s[j+1] 不相同，就要找 j+1前一個(gè)元素在next數(shù)組里的值（就是next[j]）。

所以，處理前后綴不相同的情況代碼如下：

while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了j = next[j]; // 向前回溯 }

? ? ? 3.處理前后綴相同的情況

如果s[i]?與 s[j + 1] 相同，那么就同時(shí)向后移動(dòng)i 和j 說(shuō)明找到了相同的前后綴，同時(shí)還要將j（前綴的長(zhǎng)度）賦給next[i], 因?yàn)閚ext[i]要記錄相同前后綴的長(zhǎng)度。

代碼如下：

if (s[i] == s[j + 1]) { // 找到相同的前后綴j++; } next[i] = j;

最后整體構(gòu)建next數(shù)組的函數(shù)代碼如下：

void getNext(int* next, const string& s){int j = -1;next[0] = j;for(int i = 1; i < s.size(); i++) { // 注意i從1開(kāi)始while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了j = next[j]; // 向前回溯}if (s[i] == s[j + 1]) { // 找到相同的前后綴j++;}next[i] = j; // 將j（前綴的長(zhǎng)度）賦給next[i]} }

4.使用next數(shù)組做匹配

在文本串s里 找是否出現(xiàn)過(guò)模式串t。

定義兩個(gè)下標(biāo)，j 指向模式串起始位置，i指向文本串其實(shí)位置。

那么j初始值依然為-1，為什么呢？「依然因?yàn)閚ext數(shù)組里記錄的起始位置為-1。」

i就從0開(kāi)始，遍歷文本串，代碼如下：

for (int i = 0; i < s.size(); i++)

接下來(lái)就是 s[i] 與 t[j + 1] （因?yàn)閖從-1開(kāi)始的） 進(jìn)行比較。

如果 s[i] 與 t[j + 1] 不相同，j就要從next數(shù)組里尋找下一個(gè)匹配的位置。

代碼如下：

while(j >= 0 && s[i] != t[j + 1]) {j = next[j]; }

如果 s[i] 與 t[j + 1] 相同，那么i 和 j 同時(shí)向后移動(dòng)， 代碼如下：

if (s[i] == t[j + 1]) {j++; // i的增加在for循環(huán)里 }

如何判斷在文本串s里出現(xiàn)了模式串t呢，如果j指向了模式串t的末尾，那么就說(shuō)明模式串t完全匹配文本串s里的某個(gè)子串了。

5.例題（實(shí)現(xiàn)strStr(Leetcode第28題)）

5.1題目描述

看題很容易知道是典型的KMP算法題。

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

具體過(guò)程就不再講述了，直接上代碼。

5.2代碼實(shí)現(xiàn)

class Solution { public:void getNext(int* next, const string& s) {int j = -1;next[0] = j;for(int i = 1; i < s.size(); i++) { // 注意i從1開(kāi)始while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了j = next[j]; // 向前回溯}if (s[i] == s[j + 1]) { // 找到相同的前后綴j++;}next[i] = j; // 將j（前綴的長(zhǎng)度）賦給next[i]}}int strStr(string haystack, string needle) {if (needle.size() == 0) {return 0;}int next[needle.size()];getNext(next, needle);int j = -1; // // 因?yàn)閚ext數(shù)組里記錄的起始位置為-1for (int i = 0; i < haystack.size(); i++) { // 注意i就從0開(kāi)始while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配j = next[j]; // j 尋找之前匹配的位置}if (haystack[i] == needle[j + 1]) { // 匹配，j和i同時(shí)向后移動(dòng) j++; }if (j == (needle.size() - 1) ) { // 文本串s里出現(xiàn)了模式串treturn (i - needle.size() + 1); }}return -1;} };

如果有還沒(méi)有完全明白的，可以關(guān)注微信公眾號(hào)：代碼隨想錄

bilibili視頻：https://www.bilibili.com/video/BV1M5411j7Xx/?spm_id_from=trigger_reload

此文章是根著代碼隨想錄學(xué)習(xí)之后編寫的，內(nèi)容上大致一樣，但從中受益匪淺。

總結(jié)

以上是生活随笔為你收集整理的最详细KMP算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。