Go 數據結構和算法篇：字符串匹配之 KMP 算法
KMP 算法可以說是字符串匹配算法中最知名的算法了，KMP 算法是根據三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字來命名的，算法的全稱是 Knuth Morris Pratt 算法，簡稱爲 KMP 算法。
一、核心思想
假設主串是 a，模式串是 b。在模式串與主串匹配的過程中，當遇到不可匹配的字符的時候，我們希望找到一些規律，可以將模式串往後多滑動幾位，跳過那些肯定不會匹配的情況，從而避免 BF 算法這種暴力匹配，提高算法性能。下面我們來探討下這個規律如何找到。
參考下面個主串和模式串的匹配，當模式串移動到當前位置，比對到最後一個字符 D 時，發現與主串不匹配，如果按照 BF 算法，就是把模式串往後移一位，再逐個比較，這樣做固然可以，但是效率很差：
字符串匹配算法
一個基本事實是，當 D 與主串不匹配時，我們已知前面的主串序列是 ABCDA，如果把模式串往後移一位肯定和主串不匹配，我們可不可以直接把模式串移到下一個可能和 A 匹配的主串位置？
實際上，KMP 算法正是基於這一理念，設法利用這個已知信息，不把模式串移到已經比較過的位置，繼續把它向後移，這樣綜合下來就極大提高了搜索匹配效率。
怎麼找到這個規律，確定把模式串往後移多少位呢？在模式串和主串匹配的過程中，我們把不能匹配的那個字符仍然叫作「壞字符」，把已經匹配的那段字符串叫作「好前綴」：
KMP 匹配算法圖示
在模式串和主串匹配的過程中，當遇到壞字符後，對於已經比對過的好前綴，我們只需要拿好前綴本身，在它的後綴子串中，查找最長的那個可以跟好前綴的前綴子串匹配的下標位置，然後將模式串後移到該位置即可。
這裏，我們要解釋幾個概念：
-
後綴子串：以某個字符串最後一個字符爲尾字符的子串（不包含字符串自身），比如上面的
ababa，後綴子串爲baba、aba、ba、a； -
前綴子串：以某個字符串第一個字符爲首字符的子串（不包含字符串自身），還是以
ababa爲例，前綴子串爲a、aba、abab； -
最長可匹配後綴子串：後綴子串與前綴子串最長可匹配子串，也可叫做共有子串，以
ababa爲例，自然是aba了，長度爲 3； -
最長可匹配前綴子串：與上面定義相對，即前綴子串與後綴子串最長可匹配子串。最長可匹配前綴子串和最長可匹配後綴子串肯定是一樣的。
假設壞字符所在位置是 j，最長可匹配後綴子串長度爲 k，則模式串需要後移的位數爲 j-k。每當我們遇到壞字符，就將模式串後移 j-k 位，直到模式串與對應主串字符完全匹配；如果移到最後還是不匹配，則返回 -1。這就是 KMP 算法的核心思想。
二、實現原理
瞭解了核心思想，接下來，就可以考慮如何實現 KMP 算法了，實現 KMP 算法最核心的部分是構建一個用來存儲模式串中每個前綴子串（這些前綴都有可能是好前綴）最長可匹配前綴子串的結尾字符下標數組，我們把這個數組叫做 next 數組，對於上面 ababacd 這個模式串而言，對應的 next 數組如下：
KMP 算法實現
其中，數組的下標是前綴子串結尾字符下標，數組的值是這個前綴的最長可匹配前綴子串的結尾字符下標。
有了這個 next 數組，我們就可以實現 KMP 匹配算法的核心代碼了。
三、示例代碼
下面是一個基於 KMP 算法實現的 Golang 版字符串查找函數：
1package main
2
3import "fmt"
4
5// 生成 next 數組
6func generateNext(p string) []int {
7 m := len(p)
8 next := make([]int, m, m)
9 next[0] = -1
10 next[1] = 0
11 i, j := 0, 1 // 前綴子串、後綴子串起始位置
12 // 因爲是通過最長可匹配前綴子串計算，所以 j 的值最大不會超過 m-1
13 for j < m - 1 {
14 if i == -1 || p[i] == p[j] {
15 i++
16 j++
17 // 設置當前最長可匹配前綴子串結尾字符下標
18 next[j] = i
19 } else {
20 // 如果 p[i] != p[j]，回到上一個最長可匹配前綴子串結尾字符下標
21 i = next[i]
22 }
23 }
24 return next
25}
26
27// KMP 算法實現函數
28func kmpSearch(s, p string) int {
29 n := len(s) // 主串長度
30 m := len(p) // 模式串長度
31 next := generateNext(p) // 生成 next 數組
32 i, j := 0, 0
33 for i < n && j < m {
34 // 如果主串字符和模式串字符不相等，
35 // 更新模式串壞字符下標位置爲好前綴最長可匹配前綴子串尾字符下標
36 // 然後從這個位置重新開始與主串匹配
37 // 相當於前面提到的把模式串向後移動 j - k 位
38 if j == -1 || s[i] == p[j] {
39 i++
40 j++
41 } else {
42 j = next[j]
43 }
44 }
45 if j == m {
46 // 完全匹配，返回下標位置
47 return i - j
48 } else {
49 return -1
50 }
51}
52
53// 基於 KMP 算法實現查找字符串子串函數
54func strStrV2(haystack, needle string) int {
55 // 子串長度=0
56 if len(needle) == 0 {
57 return 0
58 }
59 //主串長度=0，或者主串長度小於子串長度
60 if len(haystack) == 0 || len(haystack) < len(needle) {
61 return -1
62 }
63 // 子串長度=1時單獨判斷
64 if len(needle) == 1 {
65 i := 0
66 for ; i < len(haystack); i++ {
67 if haystack[i] == needle[0] {
68 return i
69 }
70 }
71 return -1
72 }
73
74 // 其他情況走 KMP 算法
75 return kmpSearch(haystack, needle)
76}
77
78func main() {
79 s := "Hello, 學院君!"
80 p := "學院君"
81 pos := strStrV2(s, p)
82 fmt.Printf("Find \"%s\" at %d in \"%s\"\n", p, pos, s)
83}
84
運行上述代碼，打印結果如下，說明字符串查找函數可以正常工作：
四、性能分析
KMP 算法比 BF 算法實現起來要複雜的多，不過帶來的好處是執行效率的提升，綜合 KMP 算法實現函數和 next 數組生成函數，它的時間複雜度是 O(n+m)，其中 n 是主串長度，m 是子串長度，m 和 n 的值越大，性能比 BF 算法更好，考慮到對於較長的主串，m 相對於 n 而言一般可以忽略，所以可以把 KMP 算法的時間複雜度近似看作 O(n)。
這個性能還是相當不錯的，因此，KMP 算法被廣泛用於字符串查找和匹配場景。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Xs4_Q7d0tXbVhign_dii9A