转载请注明出处：https://hts0000.github.io/
欢迎与我联系：hts_0000@sina.com
什么是KMP算法？
kmp算法是一种用于高效匹配字符串子串是否存在的算法，比如想知道文本串s中是否存在模式串p，就可以使用kmp算法。
如何实现KMP算法？
实现kmp算法分两步
- 基于模式串初始化next数组
- 使用next数组加速字符串匹配
什么是next数组？
next数组，又称为prefix数组、前缀表，其作用是记录给定字符串的所有子串中相等的前后缀长度。
什么是前缀后缀？
对于字符串cbccbcbccc，其前缀为包含首字符不包含尾字母的任意子串，其后缀为包含尾字符不包含首字符的任意子串。
前缀
1
2
3
4
5
6
|
c
cb
cbc
cbcc
...
cbccbcbcc
|
后缀
1
2
3
4
5
6
|
c
cc
ccc
bccc
...
bccbcbccc
|
对于字符串cbccbcbccc的每一个子串，我们求出它们的最长相等前后缀长度，其中子串c初始化为0。
最长相等前后缀
next数组具体实现
求next数组的代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func getNext(s string) []int {
sLen := len(s)
next := make([]int, sLen)
next[0] = 0
j := 0
for i := 1; i < sLen; i++ {
// j要保证大于0，因为下面有取j-1作为数组下标的操作
for j > 0 && s[i] != s[j] {
// 回退前一位
j = next[j - 1]
}
if s[i] == s[j] {
j++
}
next[i] = j
}
return next
}
|
求出next数组后，我们就可以利用它加速字符串的匹配。
当遇到不匹配时，就往前找一个最长相等前后缀，并移动模式串指针到他的后面，再尝试匹配
不匹配
匹配
当i==j==5时，文本串s[5] != 模式串p[5]，这时我们在next数组中往前找一位，next数组中记录了p[0:5]这个子串最长相等前后缀长度为2，意味着我们j指针只需要回退到下标为2的位置就可以继续匹配了，跳过了前面相同的部分
kmp具体实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
func kmp(s string, p string) int {
m, n := len(s), len(p)
next := make([]int, n)
// 构建next数组
for i, j := 1, 0; i < n; i++ {
for j > 0 && p[i] != p[j] { j = next[j-1] }
if p[i] == p[j] { j++ }
next[i] = j
}
// 根据next数组加速字符串匹配
for i, j := 0, 0; i < m; i++ {
for j > 0 && s[i] != p[j] { j = next[j-1] }
if s[i] == p[j] { j++ }
if j == n { return i - n + 1 }
}
// 全部匹配失败，返回-1
return -1
}
|
