做网站建设一年能赚多少,瀑布网站模板,网站秒收录工具,node.js网站开发前言
本文结合朱战立教授编著的《数据结构—使用c语言#xff08;第五版#xff09;》#xff08;以下简称为《数据结构#xff08;第五版#xff09;朱站立》#xff09;中4.4.2章节内容编写#xff0c;KMP的相关概念可参考此书4.4.2章节内容。原文中代码是C语言…前言
本文结合朱战立教授编著的《数据结构—使用c语言第五版》以下简称为《数据结构第五版朱站立》中4.4.2章节内容编写KMP的相关概念可参考此书4.4.2章节内容。原文中代码是C语言本文改用Go语言编写逻辑不变。
一、KMP介绍
KMP算法Knuth-Morris-Pratt算法是一种高效的字符串匹配算法由D.E.Knuth、J.H.Morris和V.R.Pratt提出。该算法的核心在于利用匹配失败后的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的。KMP算法的时间复杂度为O(mn)其中m和n分别代表模式串和主串的长度。
二、求next数组
next数组是KMP算法中核心概念求出next数组后在模式串元素和主串元素比较的失败的时候可以将模式串t直接偏移到以next数组中的元素为下标的位置主串指针不偏移减少了元素比较次数下面我们直接求next数组
举例
字符串s“ababbababcabac” 模式串t“ababcab” go语言版求next数组的代码如下
func GetNext(s string) []int {var next []int make([]int, len(s))next[0] -1next[1] 0// j表示当前要求next值的位置// k表示当前要和前一个字符比对的下标j, k : 1, 0for j len(s)-1 {if s[j] s[k] {next[j1] k 1kj} else if k 0 {next[j1] 0j} else {k next[k]}}return next
}执行上面代码我们能获取到next数组如下
PS D:\Project\GoWorkSpace\DataStructure go run .\0113\KMP_Algorithm.go
[-1 0 0 1 2 0 1]注以上代码的变量名称逻辑均与《数据结构第五版朱站立》中内容一致方便代码阅读 三、图解KMP匹配过程
中间部分循环过程省略主要看当模式串和主串不相等时模式串如何偏移 字符串s“ababbababcabac” 模式串t“ababcab” next数组[-1 0 0 1 2 0 1] 第一步s数组元素和t数组元素一一对比如果成功两个数组下标偏移同时1继续比较以此类推 第二步当s[4]≠t[4]时next[4]2s数组不偏移t数组偏移到t[2]比较s[4]和t[2] 第三步当s[4]≠t[2]时,next[2]0,s数组不偏移t数组偏移到t[0]比较s[4]和t[0] 第四步当s[4]≠t[0]时由于t数组已经到第一位所以s数组下标1比较s[5]和t[0] 第五步当s[5]t[0]时回到了第一步两个数组下标偏移同时1继续比较以此类推当t的下标为7时s的下标为12循环结束打印t的第一个元素在s中下标的位置即12-75
四、Go示例代码
package mainimport fmtfunc KMP(s string, t string) int {m : len(s)n : len(t)// s中当前比对的位置是i// t中当前比对的位置是ji, j : 0, 0next : GetNext(t)for i m j n {if s[i] t[j] {ij} else if j 0 {i} else {j next[j] // t串偏移偏移到next[j]下标}}if j n { // t串全部匹配return i - j} else {return -1}
}
func GetNext(s string) []int {var next []int make([]int, len(s))next[0] -1next[1] 0// j表示当前要求next值的位置// k表示当前要和前一个字符比对的下标j, k : 1, 0for j len(s)-1 {if s[j] s[k] {next[j1] k 1kj} else if k 0 {next[j1] 0j} else {k next[k]}}return next
}
func main() {t : ababcabfmt.Println(GetNext(t))fmt.Println(KMP(ababbababcabac, t))
}运行结果
PS D:\Project\GoWorkSpace\DataStructure go run .\0113\KMP_Algorithm.go
[-1 0 0 1 2 0 1]
5
