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中存在ab
cab
,那前面的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: 画图