KMP算法
0.png
KMP为字符串匹配算法，在朴素匹配算法基础中，每当匹配失败匹配串就要回到开始匹配的地方，这样字符串大的话就会很慢，特别是"abcabcabcd" "abcd"这种。 KMP利用前面匹配失败的串，比如str1 = "abcdeabcdeabp" str2 = "abcdeabp"，当在'p'匹配失败时，str2的指针可以回退到'c'的位置，因为c前面是ab，str1 c的前面也是ab，这个ab已经匹配过了，所以就不用再匹配了。而str1的指针不用回退。
如何计算str2中每个字符串匹配失败后回退到哪呢，使用一个next数组，记录每个字符匹配失败后回退的位置： next数组含义：str[i]的前缀和后缀相等的最大值，也就是匹配失败后回退到的地方。 next[0] = 0 使用两个指针i = 1, j = 0遍历str 当str[i] == str[j]时，说明当i + 1匹配失败时，它的最大前缀是j，所以next[i + 1] = j + 1 当str[i] != str[j]时，应该缩短j来继续查找str[i] == str[j]的位置，如何缩短j： a b c a b d d d a b c a b c 0 1 2 3 4 5 6 7 8 9 10 11 12 13 i = 13, j = 5的情况下 应该保证j前面的串的前缀和i前面的后缀相等，可以发现j前面的子串和i后面的子串是相等的，相等的串求最长前缀就是next[j]，所以缩小j的范围为next[j]，当j == 0时不再缩小。
func getNext(str string) []int {
next := make([]int, len(str))
next[0] = 0
i, j := 1, 0
for i < len(str)-1 {
if str[i] == str[j] {
next[i+1] = j + 1
i++
j++
} else {
if j == 0 {
i++
next[i] = 0
} else {
j = next[j]
}
}
}
return next
}next数组求出来匹配就好说了：
func strStr(haystack string, needle string) int {
if len(haystack) == 0 && len(needle) == 0 {
return 0
}
if len(needle) == 0 {
return 0
}
next := getNext(needle)
res := -1
i, j := 0, 0
for i < len(haystack) {
if j == len(needle) {
return res
}
if haystack[i] == needle[j] {
if res == -1 {
res = i - j
}
i++
j++
} else {
if j != 0 {
res = -1
} else {
i++
}
j = next[j]
}
}
if j == len(needle) {
return res
}
return -1
}
func getNext(str string) []int {
next := make([]int, len(str))
next[0] = 0
i, j := 1, 0
for i < len(str)-1 {
if str[i] == str[j] {
next[i+1] = j + 1
i++
j++
} else {
if j == 0 {
i++
next[i] = 0
} else {
j = next[j]
}
}
}
return next
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021年12月27日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读