文章目錄
- 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; //第一個位置不存在資料，為-1
for(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; //第一個位置不存在資料，為-1
for(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)
{
//不滿足條件則直接傳回false
if(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為模式串長度