0%

KMP

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,过程和找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: 画图