前言

本文結合朱戰立教授編著的《數據結構—使用c語言（第五版）》（以下簡稱為《數據結構（第五版）朱站立》）中4.4.2章節內容編寫，KMP的相關概念可參考此書4.4.2章節內容。原文中代碼是C語言，本文改用Go語言編寫，邏輯不變。

一、KMP介紹

?KMP算法?（Knuth-Morris-Pratt算法）是一種高效的字符串匹配算法，由D.E.Knuth、J.H.Morris和V.R.Pratt提出。該算法的核心在于利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數，以達到快速匹配的目的。KMP算法的時間復雜度為O(m+n)，其中m和n分別代表模式串和主串的長度。

二、求next數組

next數組是KMP算法中核心概念，求出next數組后，在模式串元素和主串元素比較的失敗的時候，可以將模式串t直接偏移到以next數組中的元素為下標的位置，主串指針不偏移，減少了元素比較次數，下面我們直接求next數組

舉例

字符串s=“ababbababcabac”
模式串t=“ababcab”
go語言版求next數組的代碼如下：

func GetNext(s string) []int {var next []int = make([]int, len(s))next[0] = -1next[1] = 0// j表示當前要求next值的位置// k表示當前要和前一個字符比對的下標j, k := 1, 0for j < len(s)-1 {if s[j] == s[k] {next[j+1] = k + 1k++j++} else if k == 0 {next[j+1] = 0j++} else {k = next[k]}}return next
}

執行上面代碼我們能獲取到next數組如下：

PS D:\Project\GoWorkSpace\DataStructure> go run .\0113\KMP_Algorithm.go
[-1 0 0 1 2 0 1]

注：以上代碼的變量名稱，邏輯均與《數據結構（第五版）朱站立》中內容一致，方便代碼閱讀

三、圖解KMP匹配過程

中間部分循環過程省略，主要看當模式串和主串不相等時，模式串如何偏移
字符串s=“ababbababcabac”
模式串t=“ababcab”
next數組=[-1 0 0 1 2 0 1]

第一步：s數組元素和t數組元素一一對比，如果成功兩個數組下標偏移同時+1繼續比較，以此類推

第二步：當s[4]≠t[4]時，next[4]=2，s數組不偏移，t數組偏移到t[2]，比較s[4]和t[2]

第三步：當s[4]≠t[2]時,next[2]=0,s數組不偏移，t數組偏移到t[0]，比較s[4]和t[0]

第四步：當s[4]≠t[0]時，由于t數組已經到第一位，所以s數組下標+1，比較s[5]和t[0]

第五步：當s[5]=t[0]時，回到了第一步，兩個數組下標偏移同時+1繼續比較，以此類推；當t的下標為7時s的下標為12，循環結束打印t的第一個元素在s中下標的位置，即：12-7=5

四、Go示例代碼

package mainimport "fmt"func KMP(s string, t string) int {m := len(s)n := len(t)// s中當前比對的位置是i// t中當前比對的位置是ji, j := 0, 0next := GetNext(t)for i < m && j < n {if s[i] == t[j] {i++j++} else if j == 0 {i++} else {j = next[j] // t串偏移，偏移到next[j]下標}}if j == n { // t串全部匹配return i - j} else {return -1}
}
func GetNext(s string) []int {var next []int = make([]int, len(s))next[0] = -1next[1] = 0// j表示當前要求next值的位置// k表示當前要和前一個字符比對的下標j, k := 1, 0for j < len(s)-1 {if s[j] == s[k] {next[j+1] = k + 1k++j++} else if k == 0 {next[j+1] = 0j++} else {k = next[k]}}return next
}
func main() {t := "ababcab"fmt.Println(GetNext(t))fmt.Println(KMP("ababbababcabac", t))
}

運行結果

PS D:\Project\GoWorkSpace\DataStructure> go run .\0113\KMP_Algorithm.go
[-1 0 0 1 2 0 1]
5