题目链接:LeetCode 459. 重复的子字符串
题意:
给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。
解题思路:
本题就是kmp算法的经典应用,n - next[n]
是原字符串的最小周期
完整代码如下:
func repeatedSubstringPattern(s string) bool {
// kmp的经典应用:求字符串的周期
//求next数组
m:=len(s)
s=" "+s
next:=make([]int,m+1)
for i,j:=2,0;i<=m;i++{
for j>0 && s[i] !=s[j+1]{
j=next[j]
}
if s[i]==s[j+1]{
j++
}
next[i] = j
}
t:=m-next[m] //周期
return t<m && m%t==0
}
标签:459,重复,next,kmp,字符串,LeetCode
From: https://www.cnblogs.com/lxing-go/p/17388884.html