文章目錄
-
-
- KMP算法基本原理
- 失效函數計算方法
- KMP算法複雜度分析
- 一些關鍵點
-
視訊講解：
KMP字元串比對算法1_哔哩哔哩 (゜-゜)つロ 幹杯~-bilibili
KMP算法基本原理
假設主串是 a，模式串是 b。在模式串與主串比對的過程中，當遇到不可比對的字元的時候，我們希望找到一些規律，可以将模式串往後多滑動幾位，跳過那些肯定不會比對的情況。
還記得我們上一節講到的好字尾和壞字元嗎？這裡類比一下，在模式串和主串比對的過程中，把不能比對的那個字元仍叫壞字元，把已經比對的那段字元串叫作好字首。
當遇到壞字元的時候，就要把模式串往後滑動，滑動過程中，隻要模式串和好字首有上下重合，前面幾個字元的比較，就相當于拿好字首的字尾子串，跟模式串的字首子串在比較。這個比較的過程能否更高效了呢？可以不用一個字元一個字元地比較了嗎？
KMP 算法就是在試圖尋找一種規律：在模式串和主串比對的過程中，當遇到壞字元後，對于已經比對過的好字首，能否找到一種規律，将模式串一次性滑動很多位？
我們隻需要拿好字首本身，在它的字尾子串中，查找最長的那個可以跟好字首的字首子串比對的。假設最長的可比對的那部分字首子串是{v}，長度是 k。我們把模式串一次性往後滑動 j-k 位，相當于，每次遇到壞字元的時候，我們就把 j 更新為 k(j為模式串中的下标)，i 不變，然後繼續比較。
為了表述起來友善，把好字首的所有字尾子串中，最長的可比對字首子串的那個字尾子串，叫作最長可比對字尾子串；對應的字首子串，叫作最長可比對字首子串。
如何求好字首的最長可比對字首和字尾子串呢？這個問題不涉及主串，隻需要通過模式串本身就能求解。是以，能不能事先計算好，在模式串和主串比對的過程中，直接拿過來用呢？
類似 BM 算法中的 bc、suffix、prefix 數組，KMP 算法也可以提前建構一個數組，用來存儲模式串中每個字首（這些字首都有可能是好字首）的最長可比對字首子串的結尾字元下标。我們把這個數組定義為 next 數組，很多書中還給這個數組起了一個名字，叫失效函數（failure function），或者字首表。
數組的下标是每個字首結尾字元下标，數組的值是這個字首的最長可以比對字首子串的結尾字元下标。這句話有點拗口，我舉了一個例子，你一看應該就懂了。
有了 next 數組，我們很容易就可以實作 KMP 算法了。我先假設 next 數組已經計算好了，先給出 KMP 算法的架構代碼。
// a, b分别是主串和模式串；n, m分别是主串和模式串的長度。
public static int kmp(char[] a, int n, char[] b, int m) {
int[] next = getNexts(b, m);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && a[i] != b[j]) { // 一直找到a[i]和b[j]
j = next[j - 1] + 1;
}
if (a[i] == b[j]) {
++j;
}
if (j == m) { // 找到比對模式串的了
return i - m + 1;
}
}
return -1;
}
簡單比對過程：
主串長度 n = 10, 模式串長度 m = 7
下标值： 0 1 2 3 4 5 6 7 8 9
主字串： a b a b a e a b a c
模式串： a b a b a c d
next數組：
下标值： 0 1 2 3 4 5
數組值： -1 -1 0 1 2 -1
i 為主串中的下标，j 為模式串中的下标
-
j = 0,i = 0: a[0] == b[0] ++j
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 1,i = 1: a[1] == b[1] ++j
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 2,i = 2: a[2] == b[2] ++j
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 3,i = 3: a[3] == b[3]
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 4,i = 4: a[4] == b[4]
主字串： a b a b a e a b a c
模式串： a b a b a c d
-
j = 5,i = 5: j = 5 > 0 && a[5] != b[5]
主字串： a b a b a e a b a c
模式串： a b a b a c d
j = next[j-1]+1 = next[5-1]+1 = 2+1 = 3
主字串： a b a b a e a b a c
模式串： ~ ~ a b a b a c d
j = 3 代表從模式串的第 j 位開始比對，因為第 j 位之前的（
aba
）已經比對好了。
…
簡單解釋一下：
- 對于主串，我們不重複通路字元，即每次比較都是從主串的的失效位（壞字元）開始的。比如上面的第一個壞字元是
e
e
- 在模式串中，0到 i 位的字首找最大相同前字尾串位數是為了第 i+1 位失配時找模式串的比對位 x ，假設從模式串的 x 位開始比對，那麼模式串的 0 到 x-1 位與主串的失配位（壞字元）往前數 x 位必須是一樣的（比如上面的
aba
失效函數計算方法
next 數組（字首表）是如何計算出來的？
當然，我們可以用非常笨的方法，比如要計算下面這個模式串 b 的 next[4]，我們就把 b[0, 4]的所有字尾子串，從長到短找出來，依次看看，是否能跟模式串的字首子串比對。很顯然，這個方法也可以計算得到 next 數組，但是效率非常低。有沒有更加高效的方法呢？
這裡的處理非常有技巧，類似于動态規劃。不過，動态規劃我們在後面才會講到，是以，我這裡換種方法解釋，也能讓你聽懂。
我們按照下标從小到大，依次計算 next 數組的值。當我們要計算 next[i]的時候，前面的 next[0]，next[1]，……，next[i-1]應該已經計算出來了。利用已經計算出來的 next 值，我們是否可以快速推導出 next[i]的值呢？
如果 next[i-1]=k-1，也就是說，子串 b[0, k-1]是 b[0, i-1]的最長可比對字首子串。如果子串 b[0, k-1]的下一個字元 b[k]，與 b[0, i-1]的下一個字元 b[i]比對，那子串 b[0, k]就是 b[0, i]的最長可比對字首子串。是以，next[i]等于 k。但是，如果 b[0, k-1]的下一字元 b[k]跟 b[0, i-1]的下一個字元 b[i]不相等呢？這個時候就不能簡單地通過 next[i-1]得到 next[i]了。這個時候該怎麼辦呢？
我們假設 b[0, i]的最長可比對字尾子串是 b[r, i]。如果我們把最後一個字元去掉，那 b[r, i-1]肯定是 b[0, i-1]的可比對字尾子串，但不一定是最長可比對字尾子串。是以，既然 b[0, i-1]最長可比對字尾子串對應的模式串的字首子串的下一個字元并不等于 b[i]，那麼我們就可以考察 b[0, i-1]的次長可比對字尾子串 b[x, i-1]對應的可比對字首子串 b[0, i-1-x]的下一個字元 b[i-x]是否等于 b[i]。如果等于，那 b[x, i]就是 b[0, i]的最長可比對字尾子串。
可是，如何求得 b[0, i-1]的次長可比對字尾子串呢？次長可比對字尾子串肯定被包含在最長可比對字尾子串中，而最長可比對字尾子串又對應最長可比對字首子串 b[0, y]。于是，查找 b[0, i-1]的次長可比對字尾子串，這個問題就變成，查找 b[0, y]的最長比對字尾子串的問題了。
按照這個思路，我們可以考察完所有的 b[0, i-1]的可比對字尾子串 b[y, i-1]，直到找到一個可比對的字尾子串，它對應的字首子串的下一個字元等于 b[i]，那這個 b[y, i]就是 b[0, i]的最長可比對字尾子串。
前面我已經給出 KMP 算法的架構代碼了，現在我把這部分的代碼也寫出來了。這兩部分代碼合在一起，就是整個 KMP 算法的代碼實作。
// b表示模式串，m表示模式串的長度
private static int[] getNexts(char[] b, int m) {
int[] next = new int[m];
next[0] = -1;
int k = -1;
for (int i = 1; i < m; ++i) {
while (k != -1 && b[k + 1] != b[i]) {
k = next[k];
}
if (b[k + 1] == b[i]) {
++k;
}
next[i] = k;
}
return next;
}
還是簡單解釋一下：
下标值： 0 1 2 3 4 5 6
模式串： a b a b a c d
next[] : -1 -1 0 1 2 -1 -1
當 i = 5：
此時
b[0, i-1]
為
ababa
，它有兩個可比對字尾子串：
- 第一個為
a
- 第二個為
aba
2
next[4] = 2
4
i-1 = 4,i = 5
現在
ababa
最長可比對字尾子串(ababa)對應的模式串的字首子串(ababa)的下一個字元(b)并不等于 b[i] (c)，那麼我們就可以考察 b[0, i-1] (也就是
ababa
)的次長可比對字尾子串 b[x, i-1] (ababa)對應的可比對字首子串 b[0, i-1-x] (ababa)的下一個字元 b[i-x] (ababa)是否等于 b[i] (c)。
- 如果等于，那 b[x, i]就是 b[0, i]的最長可比對字尾子串;
- 如果不等，就按此邏輯（次次長可比對字尾子串 ）再往前找
KMP算法複雜度分析
空間複雜度很容易分析，KMP 算法隻需要一個額外的 next 數組，數組的大小跟模式串相同。是以空間複雜度是 O(m)，m 表示模式串的長度。
KMP 算法包含兩部分，第一部分是建構 next 數組，第二部分才是借助 next 數組比對。是以，時間複雜度要從這兩部分來分析。
先來分析第一部分的時間複雜度：
計算 next 數組的代碼中，第一層 for 循環中 i 從 1 到 m-1，也就是說，内部的代碼被執行了 m-1 次。for 循環内部代碼有一個 while 循環，如果我們能知道每次 for 循環、while 循環平均執行的次數，假設是 k，那時間複雜度就是 O(k*m)。但是，while 循環執行的次數不好統計，是以我們放棄這種分析方法。
我們可以找一些參照變量，i 和 k。i 從 1 開始一直增加到 m，而 k 并不是每次 for 循環都會增加，是以，k 累積增加的值肯定小于 m。而 while 循環裡 k=next[k]，實際上是在減小 k 的值，k 累積都沒有增加超過 m，是以 while 循環裡面 k=next[k]總的執行次數也不可能超過 m。是以，next 數組計算的時間複雜度是 O(m)。
再來分析第二部分的時間複雜度：
分析的方法是類似的。i 從 0 循環增長到 n-1，j 的增長量不可能超過 i，是以肯定小于 n。而 while 循環中的那條語句 j=next[j-1]+1，不會讓 j 增長的，那有沒有可能讓 j 不變呢？也沒有可能。因為 next[j-1]的值肯定小于 j-1，是以 while 循環中的這條語句實際上也是在讓 j 的值減少。而 j 總共增長的量都不會超過 n，那減少的量也不可能超過 n，是以 while 循環中的這條語句總的執行次數也不會超過 n，是以這部分的時間複雜度是 O(n)。
是以，綜合兩部分的時間複雜度，KMP 算法的時間複雜度就是 O(m+n)。
一些關鍵點
next數組計算代碼裡的：
k = next[k]
因為前一個的最長串的下一個字元不與最後一個相等，需要找前一個的次長串，問題就變成了求0到next(k)的最長串，如果下個字元與最後一個不等，繼續求次長串，也就是下一個next(k)，直到找到，或者完全沒有。
可以看這位部落客的介紹：
如何更好地了解和掌握 KMP 算法? - 知乎
如何更好地了解和掌握 KMP 算法? - 知乎