KMP算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配
https://leetcode.cn/problems/implement-strstr/
正常判断一个字符串B是否为另一个字符串A的子串，最先想到的可能是穷举。
1
2
3
4
5
6
7
8
9
10
11
12
| for i := 0; i <= (len(A)-len(B));i++{
flag = true
for j := 0; j<len(B);j++{
if A[i] != B[i]{
flag = false
break
}
}
if flag{
return true
}
}
|
但其实不需要每次都从头开始对比A和B，在对比的时候能得到一些对下次对比有用的东西。
例如字符串:
1
2
| A: abcab|cabd
B: abcab|d
|
在第一次对比的时候，对比到最后一个字符，发现不对了。按照穷举的方法，下一个再从头对比。但是能比较明显看到，如果能直接跳过一些步骤，转成以下对比，能省很多时间。
1
2
| A: abcab|cabd
B: ab|cabd
|
因为B中是abcabd，对比到d处时，说明A中存在abcab，那前面的ab就能直接知道在A中另一个地方存在，下次对比的时候就能直接跳过。用一个数组next表示可以跳过的大小
1
2
3
4
5
| next := []int{0, 0, 0, 1, 2, 0}
A: a b c a b |c a b d
B: a b c a b |d
next: 0 0 0 1 2 0
|
下次取j为next[j]，就变成了以下：
1
2
3
| A: a b c a b |c a b d
B: a b |c a b d
next: 0 0 0 1 2 0
|
获取next
next数组指的是对比失败后能跳转到哪一位，实际上是找B中的能重头开始的重复字段，方法如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| func buildNext(needle string)[]int{
var(
pos = 1
now = 0
next = make([]int, len(needle))
)
for pos < len(needle){
if needle[pos] == needle[now]{
now++
next[pos] = now
pos++
continue
}
if now != 0{
now = next[now-1]
continue
}
next[pos] = 0
pos++
}
return next
}
func buildNext(needle string)[]int{
next := make([]int, len(needle))
for i, j := 1, 0; i < len(needle); i++ {
for j > 0 && needle[i] != needle[j] {
j = next[j-1]
}
if needle[i] == needle[j] {
j++
}
next[i] = j
}
}
|
search
再进行search，过程和找next类似，因为其实next就是一个匹配子串的过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| func strStr(haystack string, needle string) int {
next := buildNext(needle)
var(
now = 0
pos = 0
)
for now < len(haystack){
if haystack[now] == needle[pos]{
now++
pos++
}else if pos !=0 {
pos = next[pos-1]
}else{
now++
}
if pos == len(needle){
return now-pos
}
}
return -1
}
func strStr(haystack string, needle string) int {
next := buildNext(needle)
for i, j := 0, 0; i < len(haystack); i++ {
for j > 0 && haystack[i] != needle[j] {
j = next[j-1]
}
if haystack[i] == needle[j] {
j++
}
if j == m {
return i - m + 1
}
}
return -1
}
|
// TODO: 画图