# 重复的子字符串
# 题目
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
1
2
3
2
3
示例 2:
输入: s = "aba"
输出: false
1
2
2
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
1
2
3
2
3
# 思路
- 将字符串复制一份与原字符串拼接
- 将拼接好的字符串掐头去尾
- 将处理好的字符串使用
kmp匹配原字符串 - 如果匹配上，返回
true，否则返回false
示例
证明
- 我们假设复制并拼接好字符串后，与
s匹配的最小位置为i - 我们可以知道
1等于2等于3, 因为这些位置都是 s 的开头前 i 个字符串 - 我们可以知道一个性质，
s字符串前i个字符串等于后i个字符串 - 并且将
s字符串的前i个字符串移动到末尾后的字符串还是于s字符串相等 - 如果我们一直将
s前面i个字符串移动到末尾，则可以知道s的前k*i个字符串等于s的后k*i个字符串 - 上述条件满足
k*i >= n的时候为止，这说明s可以被分成长度为i的若干段，每段都相同