参照java版的写的，作者学习golang，进过一番折腾终于对kmp算法了解了，有不对的地方改正
1 package main 2 3 import ( 4 "fmt" 5 // "strings" 6 ) 7 8 //判断是否为旋转词 9 func isRotation(a, b string) bool { 10 if a == "" || b == "" { //如果俩个输入的字符串为空的话 直接return false 11 return false 12 } 13 b2 := b + b //把b相加起来拼成长 串 14 return getIndexOf(b2, a) != -1 //如果getIndexOf 为-1 则返回false 15 } 16 17 func getIndexOf(s, m string) int { //如果匹配返回相应的index 不匹配返回-1 18 if len(s) < len(m) { //如果待匹配的串比匹配的串短 则一定不匹配 返回-1 19 return -1 20 } 21 ss := []byte(s) //先将输入的 俩个string 转化成 【】byte型 方便遍历每一个字符 22 ms := []byte(m) 23 si := 0 //分别是ms ss 的遍历时的索引下标 初始化为0 24 mi := 0 25 next := getNextArray(ms) //KMP算法 生成next数组 26 for si < len(ss) && mi < len(ms) { //遍历俩个byte数组 27 if ss[si] == ms[mi] { //如果遇到俩个数组有相等的字符 28 si++ //将他们的索引游标同时后移 29 mi++ 30 } else if next[mi] == -1 { //如果匹配到某个位置不相等的话 查看他的next数组值 如果为-1，则把si 后移 31 si++ 32 } else { //如果mi当时的next数组值不是-1 33 mi = next[mi]// 则把next相应的值和 ss中si（即刚刚不匹配的地方 进行比较，，转回第一个if条件） 34 } 35 } 36 if mi == len(ms) { //如果最后匹配成功的话mi 应该是ms的长度 37 return si - mi //则返回si-mi 即刚刚匹配的开始index 38 } else { 39 return -1 //匹配到最后还没有将mi移到ms的末尾 说明不匹配 40 } 41 42 } 43 44 func getNextArray(ms []byte) []int { //得到next数组 45 if len(ms) == -1 { //最特殊的情况 ms的长度为-1 直接返回 -1 46 return []int{-1} 47 } 48 length := len(ms) 49 next := make([]int, length) //定义了一个切片 比较方便go语言 50 next[0] = -1 //第一个字符 前面没有东西 所以为-1 51 next[1] = 0 //第二个字符虽然前面有一个字符但是 它的前面只有一个所以没有最长公共前追后最 即为0 52 pos := 2 //定义的是字符串比较靠后的 位置 53 cn := 0 //定义前面的位置 为了求最长公共前缀后缀的长度 54 for pos < len(next) { //遍历整个ms 55 if ms[pos-1] == ms[cn] { //比较不匹配的前一个字符与cn是否相等 56 cn = cn + 1 57 next[pos] = cn //因为要比较最后不匹配的位置和前面最长的前缀的下一个字符 所以要加一 58 pos++ //递增 以遍历 59 } else if cn > 0 { //如果 cn 不再是0的话 意味着前面的next数组值已经算出来了 所以后面可以不用管 60 cn = next[cn] //因为刚刚直接比较cn和 pos-1 不想等 找到cn的最长公共前缀 比较 61 } else { //如果以上几步都不行 则说明 他没有 给它0吧 62 next[pos] = 0 63 pos++ 64 } 65 } 66 return next 67 } 68 func main() { 69 str1 := "yunzuocheng" 70 str2 := "zuochengyun" 71 fmt.Println(isRotation(str1, str2)) 72 }
有疑问加站长微信联系（非本文作者）
