重复的子字符串
题目
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。示例 2:
输入: s = "aba"
输出: false示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)思路
暴力的解法， 就是一个 for 循环获取子串的终止位置， 然后判断子串是否能重复构成字符串，又嵌套一个 for 循环，所以是 O(n^2) 的时间复杂度。
以第一个字母为开始的子串就可以，所以一个for循环获取子串的终止位置就行了。 而且遍历的时候 都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。
另外一个解法就是 KMP 。
解法
暴力解法：
func repeatedSubstringPattern(s string) bool {
n := len(s)
for i := 1; i <= n / 2; i++ {
if n % i == 0 {
if check(s, i) {
return true
}
}
}
return false
}
func check(s string, l int) bool {
n := len(s)
for i := l; i < n; i++ {
if s[i] != s[i - l] {
return false
}
}
return true
}KMP 解法：
func repeatedSubstringPattern(s string) bool {
return kmp(s + s, s)
}
func kmp(s, p string) bool {
n, m := len(s), len(p)
next := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && p[i] != p[j] {
j = next[j - 1]
}
if p[i] == p[j] {
j++
}
next[i] = j
}
for i, j := 0, 0; i < n; i++ {
for j > 0 && s[i] != p[j] {
j = next[j - 1]
}
if s[i] == p[j] {
j++
}
if j == m {
return true
}
}
return false
}移动匹配：
func repeatedSubstringPattern(s string) bool {
return strings.Contains((s + s)[1:len(s) * 2 - 1], s)
}