给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。(或者子字符串 "abcabc" 重复两次构成。)
这又是一道标准的KMP的题目
那么寻找重复子串怎么也涉及到KMP算法了呢？
这里就要说一说next数组了，next 数组记录的就是最长相同前后缀， 如果 next[len - 1] != 0，则说明字符串有最长相同的前后缀。且最长相等前后缀的长度为：next[len - 1] + 1（字符串长度为len）
如果len % (len - next[len - 1] ) == 0 ，即 数组长度-最长相等前后缀的长度 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串。
为什么这样整除就能说明该字符串中有重复的子字符串呢？
举个栗子??:
字符串s： a b c a b c
next[]数组：0 0 0 1 2 3对于a来说其前后缀集合都为空 =>最长相等前后缀长度为0
...
对于abca来说其前缀集合有{a,ab,abc} 后缀集合有{a,ca,bca} =>最长相等前后缀长度为1
对于abcab来说其前缀集合有{a,ab,abc,abca} 后缀集合有{b,ab,cab,bcab} =>最长相等前后缀长度为2
...
以此求得字符串s的next[]数组。
在此过程中，我们可以发现next[]表前三位（子字符串）都为0，而其后的值都是递增的，next[len-1]中存放的就是原字符串减去子字符串长度的值，也即最大相等前后缀长度，记为len2。将len-len2的值记为len1。它就是子字符串的长度，是一定可以被len整除的。
下面就可以很好写出判断条件了，整体就是构造前缀表与上述判断。
具体代码如下：
//构造前缀表
func getNext(next []int, s string) {
//初始化
j := 0
next[0] = 0
for i := 1; i < len(s); i++ {
//前后缀不相同的情况
for j > 0 && s[i] != s[j] {
j = next[j-1] //回退
}
//前后缀相同的情况
if s[i] == s[j] {
j++
}
next[i] = j
}
}
func repeatedSubstringPattern(s string) bool {
l := len(s) //字符串长度
if l == 0 {
return false
}
next := make([]int, l)
getNext(next, s)
//如果字符串的长度-最长相等前后缀长度 能被字符串长度除尽 则说明其子串能够构成该字符串
//且最长相等前后缀长度不为0
if next[l-1] != 0 && l%(l-next[l-1]) == 0 {
return true
}
return false
}
可以看到时间复杂度为O(n)
【字符串】leetcode459——重复的子字符串（KMP）
原文：https://www.cnblogs.com/zmk-c/p/14416911.html