这篇文章主要是总结一下kmp算法。所以就不写暴力遍历的逻辑了。这个算法属实是让我看了挺长时间,各种讲解博客是一点也看不进去(不是写的不详细,而是总感觉写的乱七八糟很复杂),最长公共前缀一直没理解其作用,不过反反复复的刷对应的讲解视频,卒或有所闻。
因为这个算法属实是有点抽象的,怪不得都说编程的尽头是数学,所以只是单纯的看文章中的文字可能有点痛苦,但是,don’t worry,结合代码,结合图片,多看几遍,卒或有所闻。
首先,kmp算法主要是用来判断模式串是否在文本串中出现过,如果出现过,则返回最早出现的位置的经典算法。
kmp方法的大致逻辑是通过之前判断过的信息,通过一个next数组,保存模式串里面前后最长公共子序列的长度,每次回溯,通过next数组找到前面匹配过的位置。
该算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表,算法也是由这三人姓氏进行命名。
kmp算法主要是通过一个next数组(前缀表,故也有人命名为prefix数组),这个数组主要是用来保存模式串里面前后最长公共子串(最长公共前后缀)的长度,每次回溯的时候,通过next数组找到
前面已经匹配过的位置,以此来省去大量的计算时间。
用下面代码举栗子
A := "ab ab ab a ab ab acb"
B := "ab ab acb"
打空格是为了方便观看,实际上字符之间没有空格
首先就是A B之间一个字符一个字符的进行逐一对照,然后,在对照至B字符串的c时,出现冲突,这个时候应当把B子串后移
不过这里和暴力遍历一样一位一位的往后移是不一样的,而是移动到可能成功的位置。
当A子串的后缀集合和B子串的前缀集合有交集的时候,把b子串往后移,才能成功匹配,
这里A子串的aba和B子串的aba相等即有交集,这里将B子串后移至j的位置。
然后问题来了,我们该如何获得j指针回溯的位置(B子串后移的长度)
我们需要在前面已经获得的信息里面,不遗漏的同时尽可能多的进行匹配。
所以我们就需要找到A子串后缀集合和B子串的前缀
集合的交集里面的最长元素。
因为A B子串的相同部分是完全一样的,所以A子串后缀集合和B子串的前缀集合的交集,我们也可以换一个说法:B子串的最长公共前后缀。
B子串的最长公共前后缀,在A B子串相同字符串的这个全集里里面的补集才能越小,即使B子串移动的最少,匹配的最多。
所以B子串的最长公共前后缀长度就是j指针回溯的位置
所以我们可以在A B子串匹配之前,通过B子串计算回溯位置,并将其存放在一个next数组中。
这里的next和B子串是形成了映射数组,存放的数据next[i]就是B[1]-B[i] 的最长公共前后缀的长度。
next数组有三种写法
010120
-101012(第一个赋为-1其余右移)
-10-101-1(全部减一)
减一是为了避免0位置回退到0导致死循环
接下来就分析如何一点一点的往next数组里面填充数据。
大致分为四个部分:
事先说一下:对称不是中心对称,而是中心字符块对称,比如不是abccba,而是abcabc这种对称。我刚开始也是误认为是中心对称,实则并不是这样的。
j = 0
next[0] = 0
for i = 0 i < s.size i++{
}
j = 0
next[0] = 0
for i = 0 i < s.size i++{
while j>0 && s[i] != s[j]{
j = next[j-1]
}
/*因为j向前回退不是只进行一次,而是有可能进行多次回退,所以这里不能使用if判断而是应该使用while*/
}
简单解释一下为什么前后缀不同的时候要看前一位的next数组的值 a、当当前字符的前一个字符的对称程度为0的时候,只要将当前字符与子串第一个字符进行比较。这个很好理解啊,前面都是0,说明都不对称了,如果多加了一个字符,要对称的话最多是当前的和第一个对称。比如agcta这个里面t的是0,那么后面的a的对称程度只需要看它是不是等于第一个字符a了。 b、按照这个推理,我们就可以总结一个规律,不仅前面是0,如果前面一个字符的next值是1,那么我们就把当前字符与子串第二个字符进行比较,因为前面的是1,说明前面的字符已经和第一个相等了,如果这个又与第二个相等了,说明对称程度就是2了。有两个字符对称了。比如上面agctag,倒数第二个a的next是1,说明它和第一个a对称了,接着我们就把最后一个g与第二个g比较,又相等,自然对称程度就累加了,就是2了。
j = 0
next[0] = 0
for i = 0 i < s.size i++{
while j>0 && s[i] != s[j]{
j = next[j-1]
}
if s[i] == s[j]{
j++
//因为这里判断出来前后缀相同,所以这里的代表着最长相等前后缀的j自然要+1
}
}
j = 0
next[0] = 0
for i = 0 i < s.size i++{
while j>0 && s[i] != s[j]{
j = next[j-1]
}
if s[i] == s[j]{
j++
//因为这里判断出来前后缀相同,所以这里的代表着最长相等前后缀的j自然要+1
next [i] = j
}
}
这里是一个完整的kmp算法的代码。
package main
import (
"fmt"
)
// kmpSearch 进行 KMP 算法的字符串匹配
func kmpSearch(text, pattern string) {
next := buildNext(pattern)
n := len(text)
m := len(pattern)
i := 0 // text 的索引
j := 0 // pattern 的索引
for i < n {
if text[i] == pattern[j] {
i++
j++
}
if j == m {
fmt.Printf("Found pattern at index %d\n", i-j)
j = next[j-1]
} else if i < n && text[i] != pattern[j] {
if j != 0 {
j = next[j-1]
} else {
i++
}
}
}
}
// buildNext 构建模式串的 next 数组
func buildNext(pattern string) []int {
m := len(pattern)
next := make([]int, m)
j := 0
i := 1
for i < m {
if pattern[i] == pattern[j] {
j++
next[i] = j
i++
} else {
if j != 0 {
j = next[j-1]
} else {
next[i] = 0
i++
}
}
}
return next
}
func main() {
text := "ABABDABACDABABCABAB"
pattern := "ABABCABAB"
kmpSearch(text, pattern)
}
kmpSearch
函数:
next := buildNext(pattern)
:调用 buildNext
函数构建模式串的 next
数组。n := len(text)
和 m := len(pattern)
:分别获取文本串和模式串的长度。i := 0
和 j := 0
:初始化文本串和模式串的索引。for i < n
:遍历文本串。
if text[i] == pattern[j]
:如果当前字符匹配,则同时移动 i
和 j
。if j == m
:如果 j
达到模式串的长度,说明找到了一个匹配,输出匹配的起始位置,然后通过 next[j-1]
继续匹配下一个可能的子串。else if i < n && text[i] != pattern[j]
:如果字符不匹配:
if j != 0
:如果 j
不为 0,通过 next[j-1]
找到前面匹配过的位置 j
。else
:如果 j
为 0,直接移动 i
。
buildNext
函数:
m := len(pattern)
:获取模式串的长度。next := make([]int, m)
:初始化 next
数组,其长度为模式串的长度,每个元素初始值为 0。j := 0
和 i := 1
:初始化 j
和 i
的索引。for i < m
:遍历模式串。
if pattern[i] == pattern[j]
:如果当前字符匹配,则最长公共前后缀长度 j
加 1,并将其赋值给 next[i]
,然后移动 i
。else
:如果字符不匹配:
if j != 0
:如果 j
不为 0,通过 next[j-1]
找到前面匹配过的位置 j
。else
:如果 j
为 0,将 next[i]
设为 0,然后移动 i
。
buildNext
函数:
m := len(pattern)
:获取模式串的长度。next := make([]int, m)
:初始化 next
数组,其长度为模式串的长度,每个元素初始值为 0。j := 0
和 i := 1
:初始化 j
和 i
的索引。for i < m
:遍历模式串。
if pattern[i] == pattern[j]
:如果当前字符匹配,则最长公共前后缀长度 j
加 1,并将其赋值给 next[i]
,然后移动 i
。else
:如果字符不匹配:
if j != 0
:如果 j
不为 0,通过 next[j-1]
找到前面匹配过的位置 j
。else
:如果 j
为 0,将 next[i]
设为 0,然后移动 i
。视频评论区有一句鸡汤,这里分享出来。
一个人能能走的多远不在于他在顺境时能走的多快,而在于他在逆境时多久能找到曾经的自己。
----KMP
参考
https://blog.csdn.net/yearn520/article/details/6729426
https://www.bilibili.com/video/BV1234y1y7pm/?spm_id_from=333.337.search-card.all.click
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。