数科院博客园 - KMP
type: channel
link: https://blog.icsc.vip/index.php/tag/KMP/
items: KMP算法--golang

KMP算法--golang
type: item
date: 2021-08-11T08:06:00+00:00
description: 串匹配--KMP算法next数组首先我们先要了解一下什么是字符串的前缀和后缀前缀字符串的前缀是指字符串的任意首部。比如：望，望江，望江楼，望江楼上.......后缀字符串的任意尾部是字符串的后缀。比如：流，江流，江江流，望江江流......前缀和后缀的公共子串字符串前缀和后缀相同的字串。比如：“望江楼上望” 中的 字串“望”， “望江楼上望江”中的“望江”图解求next数组第一个字符前没有字符串，对应数组的值为-1（默认的） 第二个字符前的字符串，没有公共子串（从这里开始，next数组对应的值是.公共子串的长度）第三个字符前的字符串，没有公共子串第四个字符前的字符串，没有公共子串第五个字符前的字符串，没有公共子串第六个字符前的字符串，出现了公共子串“望”，长度是1，对应数组的值：1 第七个字符前的字符串，出现了公共子串“望江”，长度是2，对应数组的值：2第八个字符前的字符串，没有公共子串代码实现package main import "fmt" func main() { var str string = "望江楼上望江江流" text := []rune(str) next := next(text) for _, i2 := range next { fmt.Printf("%d，", i2) } } func next(str []rune) []int { strLength := len(str) next := make([]int, strLength, strLength) next[0] = -1 k := -1 //记录公共子串的长度 j := 0 for j < strLength-1 { if k == -1 || str[k] == str[j] { k++ j++ next[j] = k } else { k = next[k] } } return next } 运行结果：-1，0，0，0，0，1，2，0，kmp算法KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。图解第一次匹配第四个字符失配。字串的初始值为对应的第四个字符的next数组中的值 0。第二次匹配由于前三个是匹配的，而第四个字符失配，没有公共字串，那么无需再比较前三个字符。这里的长串索引没有初始化，还是上次失配的值，就是3短串初始值是0第三次匹配第三个字符失配，短串初始值为对应的next数组中的0第四次匹配第一个字符失配（就将长串索引+1，字串索引+1，代码中会有一个判断）第五次匹配第一个字符失配（就将长串索引+1，字串索引+1，代码中会有一个判断）第六次匹配第七个字符失配。出现了公共字串“望江”，下次字串的索引初始值是对应的2。第七次匹配长串的索引值还是上次失配的地方的值：14短串初始值：2后面的就省略了........代码package main import "fmt" func main() { var shortStr string = "望江楼上望江江流" var longStr string = "望江楼，望江流，望江楼上望江流，江楼千古，江流千古" shortText := []rune(shortStr) longText := []rune(longStr) result := kmp(shortText, longText) if result == -1 { fmt.Println("没有匹配到") }else { fmt.Println("匹配到首次出现的索引位置是：", result) } } func kmp(shortStr, longStr []rune) int{ shortStrLen := len(shortStr) longStrLen := len(longStr) if shortStrLen > longStrLen { return -1 } var i int = 0 //长串索引 var j int = 0 //短串索引 next := next(shortStr) for i < longStrLen { if j== -1 || longStr[i] == shortStr[j] { i++; j++; }else { j = next[j]; } if j == shortStrLen { return i - j } } return -1 } func next(str []rune) []int { strLength := len(str) next := make([]int, strLeng…