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