Go 數據結構和算法篇（十二）：字符串匹配之 KMP 算法
KMP 算法可以說是字符串匹配算法中最知名的算法了，KMP 算法是根據三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字來命名的，算法的全稱是 Knuth Morris Pratt 算法，簡稱為 KMP 算法。
一、核心思想
假設主串是 a，模式串是 b。在模式串與主串匹配的過程中，當遇到不可匹配的字符的時候，我們希望找到一些規(guī)律，可以將模式串往后多滑動幾位，跳過那些肯定不會匹配的情況，從而避免 BF 算法這種暴力匹配，提高算法性能。下面我們來探討下這個規(guī)律如何找到。
參考下面?zhèn)€主串和模式串的匹配，當模式串移動到當前位置，比對到最后一個字符 D 時，發(fā)現與主串不匹配，如果按照 BF 算法，就是把模式串往后移一位，再逐個比較，這樣做固然可以，但是效率很差：
一個基本事實是，當 D 與主串不匹配時，我們已知前面的主串序列是 ABCDA，如果把模式串往后移一位肯定和主串不匹配，我們可不可以直接把模式串移到下一個可能和 A 匹配的主串位置？
實際上，KMP 算法正是基于這一理念，設法利用這個已知信息，不把模式串移到已經比較過的位置，繼續(xù)把它向后移，這樣綜合下來就極大提高了搜索匹配效率。
怎么找到這個規(guī)律，確定把模式串往后移多少位呢？在模式串和主串匹配的過程中，我們把不能匹配的那個字符仍然叫作「壞字符」，把已經匹配的那段字符串叫作「好前綴」：
在模式串和主串匹配的過程中，當遇到壞字符后，對于已經比對過的好前綴，我們只需要拿好前綴本身，在它的后綴子串中，查找最長的那個可以跟好前綴的前綴子串匹配的下標位置，然后將模式串后移到該位置即可。
這里，我們要解釋幾個概念：
后綴子串：以某個字符串最后一個字符為尾字符的子串（不包含字符串自身），比如上面的
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 數組如下：
其中，數組的下標是前綴子串結尾字符下標，數組的值是這個前綴的最長可匹配前綴子串的結尾字符下標。
有了這個 next 數組，我們就可以實現 KMP 匹配算法的核心代碼了。
三、示例代碼
下面是一個基于 KMP 算法實現的 Golang 版字符串查找函數：
package main
import "fmt"
// 生成 next 數組
func generateNext(p string) []int {
m := len(p)
next := make([]int, m, m)
next[0] = -1
next[1] = 0
i, j := 0, 1 // 前綴子串、后綴子串起始位置
// 因為是通過最長可匹配前綴子串計算，所以 j 的值最大不會超過 m-1
for j < m - 1 {
if i == -1 || p[i] == p[j] {
i++
j++
// 設置當前最長可匹配前綴子串結尾字符下標
next[j] = i
} else {
// 如果 p[i] != p[j]，回到上一個最長可匹配前綴子串結尾字符下標
i = next[i]
}
}
return next
}
// KMP 算法實現函數
func kmpSearch(s, p string) int {
n := len(s) // 主串長度
m := len(p) // 模式串長度
next := generateNext(p) // 生成 next 數組
i, j := 0, 0
for i < n && j < m {
// 如果主串字符和模式串字符不相等，
// 更新模式串壞字符下標位置為好前綴最長可匹配前綴子串尾字符下標
// 然后從這個位置重新開始與主串匹配
// 相當于前面提到的把模式串向后移動 j - k 位
if j == -1 || s[i] == p[j] {
i++
j++
} else {
j = next[j]
}
}
if j == m {
// 完全匹配，返回下標位置
return i - j
} else {
return -1
}
}
// 基于 KMP 算法實現查找字符串子串函數
func strStrV2(haystack, needle string) int {
// 子串長度=0
if len(needle) == 0 {
return 0
}
//主串長度=0，或者主串長度小于子串長度
if len(haystack) == 0 || len(haystack) < len(needle) {
return -1
}
// 子串長度=1時單獨判斷
if len(needle) == 1 {
i := 0
for ; i < len(haystack); i++ {
if haystack[i] == needle[0] {
return i
}
}
return -1
}
// 其他情況走 KMP 算法
return kmpSearch(haystack, needle)
}
func main() {
s := "Hello, 學院君!"
p := "學院君"
pos := strStrV2(s, p)
fmt.Printf("Find \"%s\" at %d in \"%s\"\n", p, pos, s)
}
運行上述代碼，打印結果如下，說明字符串查找函數可以正常工作：
四、性能分析
KMP 算法比 BF 算法實現起來要復雜的多，不過帶來的好處是執(zhí)行效率的提升，綜合 KMP 算法實現函數和 next 數組生成函數，它的時間復雜度是 O(n+m)，其中 n 是主串長度，m 是子串長度，m 和 n 的值越大，性能比 BF 算法更好，考慮到對于較長的主串，m 相對于 n 而言一般可以忽略，所以可以把 KMP 算法的時間復雜度近似看作 O(n)。
這個性能還是相當不錯的，因此，KMP 算法被廣泛用于字符串查找和匹配場景。
（本文完）
學習過程中有任何問題，可以通過下面的評論功能或加入「Go 語言研習社」與學院君討論：
本系列教程首發(fā)在 geekr.dev，你可以點擊頁面左下角閱讀原文鏈接查看最新更新的教程。