文章目錄

• KMP
• 原理
• next數組的構建
• 代碼實現

---

KMP

一提到字符串匹配算法，想必大家腦海中想到的第一個必然就是KMP算法，KMP算法的全稱叫做KnuthMorrisPratt算法，與上一篇博客中介紹的BM算法一樣，它的核心也是通過滑動來減少不必要的匹配。

---

原理

與BM算法不同，KMP算法是從前往后進行比較的，并且其將專注點放在已匹配的前綴上，為了方便理解，在這里我們還是使用BM算法中的好前綴和壞字符的概念。

例如下列字符串

還是老樣子，我們試圖在已匹配的前綴中找到某種規律，使得我們能夠一下進行大量的滑動，我們此時就對好前綴進行分析。

此時我們發現，對于好前綴來說，其存在兩組完全相同的前綴和后綴，分別是aba和a。

此時我們就可以利用這個相同的后綴，直接將模式串對其到后綴的起始位置，為了保證偏移量最大，我們選擇其中最長的那一組，如下圖

為了表述方便，我將這組前后綴子串分別稱為最長可匹配前綴子串和最長可匹配前綴子串

KMP的整體思路就是在已匹配的前綴當中尋找到最長可匹配后綴子串和最長可匹配前綴子串，在下一輪直接把兩者對齊，從而實現模式串的快速滑動

---

next數組的構建

為了避免每次都要去尋找這組最長匹配的前后綴，我們將其緩存到一個數組中，等到使用的時候再去取，這個數組也就是我們經常提到的next數組，而它的構建也是KMP算法中最難理解的地方

數組的下標是每個前綴結尾字符下標，數組的值是這個前綴的最長可以匹配前綴子串的結尾字符下標。

那么要如何構建next數組呢?我們需要借助到動態規劃和回溯的思想，在大部分算法書和博客中都將這塊描述的十分復雜，下面我就將其分解成多個問題，來方便理解

next數組構建時存在以下兩種情況，為了方便表述，我將后綴起點定為i，前綴起點定為j

前綴和后綴對應的位置匹配

前綴和后綴對應的位置不匹配

前綴和后綴對應的位置匹配
由于第一個位置只有一個字符，不存在前綴和后綴一說，所以初值為-1，其他位置全部初始化為0。從第一個位置開始遍歷。

我們可以采用動態規劃的方法，如果當前位置的前綴和后綴匹配時，則匹配前綴的長度加一，而我們當前的前綴[0, i]又是從[0, i - 1]推導而來，所以它們之間的關系也就是next[i] = next[i - 1] + 1。

簡而言之，如果當前的字符匹配，則當前next的值為上一個位置的值加一。

前綴和后綴對應的位置不匹配
假設此時已匹配前綴為GTGTGC，此時GTGT與GTGC中的T和C并不相同，又如何處理呢？

此時我們無法從上一個位置來推出這一個位置的值，而在這個壞字符出現之前，GTG又是一組可匹配的最長前綴子串，所以我們可以將問題GTGTGC轉換為求后綴GTGC的最長可匹配前綴

也就是將j給回溯到next[j]的位置

但是由于T和C還是不相同，所以再求后綴GC的最長可匹配前綴

此時繼續回溯

由于G不等于C，所以該位置沒有任何匹配的前綴，next為0

簡而言之，如果最長可匹配后綴子串無法與前綴匹配，則嘗試尋找當前的后綴子串中是否存在一個可匹配的前綴子串，將j回溯到next[j]的位置

void getNext(const string& pattern, vector<int>& next) {int i , j = 0;next[0] = -1; //第一個位置不存在數據，為-1for(int i = 1; i < next.size(); i++){//如果當前位置沒有匹配前綴，則回溯到求當前后綴的最長可匹配前綴while(j != 0 && pattern[j] != pattern[i]){j = next[j];}//如果該位置匹配，則在next數組在上一個位置的基礎上加一if(pattern[j] == pattern[i]){j++;}next[i] = j;} }

---

代碼實現

KMP的完整實現如下

#include<string> #include<iostream> #include<vector>using namespace std;//獲取next數組 void getNext(const string& pattern, vector<int>& next) {int i , j = 0;next[0] = -1; //第一個位置不存在數據，為-1for(int i = 1; i < next.size(); i++){//如果當前位置沒有匹配前綴，則回溯到求當前后綴的最長可匹配前綴while(j != 0 && pattern[j] != pattern[i]){j = next[j];}//如果該位置匹配，則在next數組在上一個位置的基礎上加一if(pattern[j] == pattern[i]){j++;}next[i] = j;} }int knuthMorrisPratt(const string& str, const string& pattern) {//不滿足條件則直接返回falseif(str.empty() || pattern.empty() || str.size() < pattern.size()){return -1;}int i = 0, j = 0;int len1 = str.size(), len2 = pattern.size();vector<int> next(pattern.size(), -1); //next數組表示第j - 1個位置的匹配前綴的起始下標getNext(pattern, next);for(int i = 0; i < len1; i++){//找到最長的可匹配前綴while(j > 0 && str[i] != pattern[j]){j = next[j - 1] + 1; //直接滑動到匹配的前綴位置，并繼續匹配下一個位置}//如果匹配成功，則繼續匹配下一個位置if(str[i] == pattern[j]){j++;}if(j == len2){return i - len2 + 1; //返回主串中匹配子串的起始下標}}return -1; }

空間復雜度
KMP算法需要借助到一個next數組，所以空間復雜度為O(M)，M為模式串長度
時間復雜度
時間復雜度主要包含兩個部分，next數組的構建以及對主串的遍歷。
其中next數組構建的時間復雜度可以估算為O(M)，第二步主串的循環為O(N)。所以KMP算法的時間復雜度為O(N + M)，N為主串長度，M為模式串長度

總結

以上是生活随笔為你收集整理的字符串匹配算法(三)：KMP(KnuthMorrisPratt)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。