先上代码：
package kmp
// KMP "a" is main string and "b" is model string
func KMP(a, b string) int {
n := len(a)
m := len(b)
next := getNext(b)
i, j := 0, 0
for i < n && j < m {
if j == -1 || a[i] == b[j] {
i++
j++
} else {
j = next[j]
}
}
// totally match
if j == m {
return i - j
}
return -1
}
func getNext(b string) []int {
m := len(b)
next := make([]int, m, m)
next[0] = -1
next[1] = 0
i, j := 0, 1 // start position
for j < m-1 {
if i == -1 || b[i] == b[j] {
i++
j++
next[j] = i
} else {
i = next[i]
}
}
return next
}
func KMPSearch(a, b string) int {
if len(b) == 0 {
return -1
}
if len(a) == 0 || len(a) < len(b) {
return -1
}
if len(b) == 1 {
i := 0
for ; i < len(a); i++ {
if a[i] == b[0] {
return i
}
}
return -1
}
return KMP(a, b)
}
package kmp
import (
"github.com/magiconair/properties/assert"
"strings"
"testing"
)
func TestKMP(t *testing.T) {
expected := "你好我*abc1234hell11111*hell****"
a := "你好我日abc1234hell11111日hell日日日日"
b := "日"
pattern := "*"
p := KMPSearch(a, b)
if p != -1 {
assert.Equal(t, strings.ReplaceAll(a, b, pattern), expected)
} else {
t.Log("not existed")
}
}
KMP 算法的核心思想和 BM 算法非常相近，假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，试图找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
KMP 算法试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，找到一种规律，将模式串一次性滑动很多位。只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。
上面的代码中，最关键的是getNext 函数。getNext 生成一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。很多书中还给这个数组起了一个名字，叫失效函数（failure function）。
KMP 算法比 BF 算法实现起来要复杂的多，不过带来的好处是执行效率的提升，综合 KMP 算法实现函数和 next 数组生成函数，它的时间复杂度是 O(n+m)，其中 n 是主串长度，m 是子串长度，m 和 n 的值越大，与 BF 算法相比，性能越好，考虑到对于较长的主串，m 相对于 n 而言一般可以忽略，所以可以把 KMP 算法的时间复杂度近似看作 O(n)。
