一、题目
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
二、解法
暴力:
若为true,则该子串必定是前缀,且满足\(s[j]==s[j-i]\)(i为子串长度)。小优化:由于子串重复次数至少为2,则子串长度不能超过字符串长度一半。
func repeatedSubstringPattern(s string) bool {
len:=len(s)
for i:=1;i<=len/2;i++{
if len%i==0{
match:=true
for j:=i;j<len;j++{
if s[j]!=s[j-i]{
match=false
break
}
}
if match{
return true
}
}
}
return false
}
KMP:
求出next数组后,判断 \(n\%(n-next[n-1])==0\)
func repeatedSubstringPattern(s string) bool {
next:=buildNext(s)
len:=len(s)
return next[len-1]!=0&&len%(len-next[len-1])==0
}
func buildNext(s string) []int{
len:=len(s)
next:=make([]int,len)
for i,now:=1,0;i<len;{
if s[i]==s[now]{
next[i]=now+1
now++
i++
}else{
if now!=0{
now=next[now-1]
}else{
i++
}
}
}
return next
}