最近研究了一下kmp算法(Knuth-Morris-Pratt),百度了好多帖子,看的稀里糊涂。为了自己可以简单理解(还有最重要的next数组),也为了自己以后忘记的话不用再满世界百度,索性将自己的理解记录下来
用途
KMP算法,具体谁发明的就不说了,它主要的用途就是查找字符串,查找字符串"ab"(目标字符串)在字符串"abc"(待查找字符串)中出现的位置。换句话说,就是查找字符串"abc"是否包含字符串"ab",如果包含,返回包含的起始位置
如下两个字符串:
str = "dabxabxababxabwabxad" (待查找字符串)
ptr = "abxabwabxad" (目标字符串)
需要计算str中是否含有ptr,如果有,返回str中出现的起始位置,如果没有,返回-1
通过肉眼观察我们发现,str中是包含ptr的
dabxabxababxabwabxad
,ptr是在str中第9位(下标从0开始)开始出现的,那么返回的结果就是9
实现
先看一下go的实现代码(只是为了方便才用go实现,使用map生成的next数组效率很低)
func main() {
str := "dabxabxababxabwabxad"
ptr := "abxabwabxad"
i := kmp(str, ptr)
fmt.Println(i)
}
func next(findStr string, num int) (next map[int]int) {
k := 0
next = make(map[int]int, num)
next[0] = k
for i := 1; i < num; i++ {
for k > 0 && findStr[k] != findStr[i] {
k = next[k-1]
}
if findStr[k] == findStr[i] {
k++
}
next[i] = k
}
return next
}
func kmp(str string, findStr string) int {
strL := len(str)
findStrL := len(findStr)
k := 0
nextArr := next(findStr, findStrL)
for i := 0; i < strL; i++ {
for k > 0 && findStr[k] != str[i] {
k = nextArr[k-1]
}
if findStr[k] == str[i] {
k++
}
if k == findStrL {
return i - k + 1
}
}
return -1
}
算法由两部分组成
1、计算ptr每一位及之前的字符串中,前缀和后缀公共部分的最大长度的next数组
2、匹配ptr和str,当ptr失配时,利用next数组,实现ptr的最大后移,从而避免不必要的匹配,减少匹配次数
by smoke_zl
计算next数组
前缀和后缀公共部分的最大长度
一个字符串ababa
,他的前缀是可以是a
,ab
,aba
,abab
(不包含最后一位),后缀是a
,ba
,aba
,baba
(不包含第一位)
前缀后缀公共部分就是a
和aba
,公共部分最大就是aba
,公共部分的最大长度就是3
next数组
next数组是ptr每一位及之前的字符串中,前缀和后缀公共部分的最大长度的集合
比如ptr字符串的长度是11(abxabwabxad),那么next数组就有11个元素
- next[0]表示ptr前一位
a
中,前缀和后缀公共部分的最大长度,由于a
中没有前缀和后缀,所以next[0]=0 - next[1]表示ptr前两位
ab
中,前缀和后缀公共部分的最大长度,ab
的前缀是a
,后缀是b
,没有公共部分,所以next[1]=0
同理 - next[2]=0(
abx
中无公共前后缀) - next[3]=1(
abxa
公共前后缀最长为a
,长度为1) - next[4]=2(
abxab
公共前后缀最长为ab
,长度为2) - next[5]=0(
abxabw
中无公共前后缀) - next[6]=1(
abxabwa
公共前后缀最长为a
,长度为1) - next[7]=2(
abxabwab
公共前后缀最长为ab
,长度为2) - next[8]=3(
abxabwabx
公共前后缀最长为abx
,长度为3) - next[9]=4(
abxabwabxa
公共前后缀最长为abxa
,长度为4) - next[10]=0(
abxabwabxad
中无公共前后缀)
下面用图文来解释,next函数是如何计算next数组的值的
image上图第一行,左边i值
为ptr下标的值,中间是ptr字符串的每一位,右边是对应的next[i]值
,从 i = 0 开始,分析每一行的计算过程
- i = 0
由于字符串的前一位只有一个字符,是没有前后缀的,所以next[0] = 0
,对应代码
k := 0
next[0] = k
-
i = 1
从上一次循环,可知 k = 0,既不满足代码中k > 0 && findStr[k] != findStr[i]
的判断,也不满足findStr[k] == findStr[i]
的判断,所以最后next[i] = k
,也就是next[1] = 0
-
i = 2
同上,k = 0,next[2] = 0
-
i = 3
k = 0,满足findStr[k] == findStr[i]
的判断,执行k++
,这时 k = 1,最后next[i] = k
,也就是next[3] = 1
-
i= 4
k = 1, 满足findStr[k] == findStr[i]
的判断,执行k++
,这时 k = 2,最后next[i] = k
,也就是next[4] = 2
-
i = 5
k = 2,满足k > 0 && findStr[k] != findStr[i]
,执行k = next[k-1]
,k = next[2-1] = next[1] = 0
很多人(包括我)都很不理解k = next[k-1]
这行代码的意思,这里先不做解释,后边 i = 10 的时候说 -
i = 6...i = 9
i = 6 到 i = 9 的逻辑和上边相似,就不重复说了,可以参照着图看 -
i = 10
image
k = 4,满足k > 0 && findStr[k] != findStr[i]
,执行k = next[k-1]
,在这里仔细说下k = next[k-1]
的意思
当 i = 9 执行完后,字符串指针为下图的样子,此时前后缀公共部分的最大字符串为abxa
再看
imageabxa
字符串,abxa
字符串的前后缀公共部分的最大字符串为a
,所以 i = 9 时,前后缀公共部分可以分解为下图的形式所以当 i = 10 时,如果
imagek > 0 && findStr[k] != findStr[i]
,也就是 k指向的b不等于i指向的d,如图那么k指针就会执行
imagek = next[k-1]
回到前缀的公共前缀
继续比较,也就是这样,就保证最效率的匹配
匹配字符串
第一部分利用next函数得到了next数组,下一步执行kmp函数,对ptr和str进行匹配,并当ptr和str失配时,利用next数组,进行最大位移,由于kmp函数和next函数差不多,这里就不详细讲了,直接上图
image参考:
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
https://blog.csdn.net/qq_30974369/article/details/74276186
网友评论