Golang leetcode459 拼接+kmp算法

本文主要是介绍Golang leetcode459 拼接+kmp算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

重复的子字符串 leetcode459
- 暴力
- 字符串拼接+KMP

重复的子字符串 leetcode459

暴力

func repeatedSubstringPattern(s string) bool {L := len(s)record := falsefor i := 1; i < L/2+1; i++ {if L%i != 0 {continue}num := L / ifor ; num > 0; num-- {if s[:i] != s[(num-1)*i:num*i] {record = falsebreak}record = true}if record == true {return record}}return record}

字符串拼接+KMP

如果有一个子字符串重复可以构成原字符串，则两个字符串拼接后其中一定包含一个原字符串
nnn=s，则s+s=nn|nnn|n中也包含一个s
abc=s，则s+s=a|bcab|c，其中bca，cab一定不为s

主要函数部分：

// 移动匹配-----------------------------------
func repeatedSubstringPattern(s string) bool {sDouble := s + sL := len(sDouble)if strStr(sDouble[1:L-1], s) == -1 {return false}return true
}

KMP函数部分：kmp算法相关请移步这篇文章

// kmp算法，用空间换时间
func strStr(haystack string, needle string) int {//获取next数组
next := initNext(needle)//主串长度
L := len(haystack)//目标匹配长度，即needle的长度
target := len(needle)//匹配字符串中指针位置
j := 0//i为主串中指针的位置
for i := 0; i < L; {// 如果匹配上了
if haystack[i] == needle[j] {
if j == target-1 {
return i - target + 1
}
j++
i++
} else { //如果没匹配上//跟计算next数组有异曲同工之妙
if j > 0 {
j = next[j-1]
} else {
i++
}}
}return -1
}// 此函数用来初始化next数组
func initNext(needle string) []int {
//后缀中末尾  abc中c
i := 1//前缀中末尾;同时在这里也有着记录最长公共串长度的作用，二者本质是一样的
j := 0L := len(needle)//初始化next数组；next[0]默认为0，因为对于一个字母我们不认为其具有前后缀，后续也不会再对next[0]进行赋值
next := make([]int, L)//求next数组过程中，我们的i不回退，采用类似于动态规划的思想，也是我们这里的循环条件
for i < L {//如果前后缀匹配
if needle[i] == needle[j] {//前缀末尾向后移一位，同时代表长度+1
j++//当前后缀末尾所在位置的最长子串即为j
//最长子串是有基础的，如果next[2]=2，那么next[3]的可能性为3或者0,这里是为3的情况
next[i] = j//后缀末尾向后移一位
i++} else { //如果前后缀不匹配//当j>0，说明仍旧处于回退的过程
if j > 0 {
j = next[j-1]
} else { //如果j=0，并且前后缀依旧不匹配，则长度计数应该重新从0开始//这里是为0的情况
next[i] = j//后缀末尾向后移
i++
}
}
}
//返回next数组
return next
}