给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
- 输入: "abab"
- 输出: True
- 解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
- 输入: "aba"
- 输出: False
示例 3:
- 输入: "abcabcabcabc"
- 输出: True
- 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
思路
移动匹配
当一个字符串s：abcabc，内部由重复的子串组成，那么这个字符串的结构一定是这样的：
也就是由前后相同的子串组成。
那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前面的子串做后串，就一定还能组成一个s，如图：
当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。
以上证明的充分性，接下来证明必要性：
如果有一个字符串s，在 s + s 拼接后， 不算首尾字符，如果能凑成s字符串，说明s 一定是重复子串组成。
如图，字符串s，图中数字为数组下标，在 s + s 拼接后， 不算首尾字符，中间凑成s字符串。
图中，因为中间拼接成了s，根据红色框 可以知道 s[4] = s[0]， s[5] = s[1]， s[0] = s[2], s[1] = s[3] s[2] = s[4] ,s[3] = s[5]
以上相等关系我们串联一下：
s[4] = s[0] = s[2]
s[5] = s[1] = s[3]
即：s[4],s[5] = s[0],s[1] = s[2],s[3]
说明这个字符串，是由 两个字符 s[0] 和 s[1] 重复组成的！
这里可以有录友想，凭什么就是这样组成的s呢，我换一个方式组成s 行不行，如图：
s[3] = s[0]，s[4] = s[1] ，s[5] = s[2]，s[0] = s[3]，s[1] = s[4]，s[2] = s[5]
以上相等关系串联：
s[3] = s[0]
s[1] = s[4]
s[2] = s[5]
s[0] s[1] s[2] = s[3] s[4] s[5]
和以上推导过程一样，最后可以推导出，这个字符串是由 s[0] ，s[1] ，s[2] 重复组成。
如果是这样的呢，如图：
s[1] = s[0]，s[2] = s[1] ，s[3] = s[2]，s[4] = s[3]，s[5] = s[4]，s[0] = s[5]
以上相等关系串联
s[0] = s[1] = s[2] = s[3] = s[4] = s[5]
最后可以推导出，这个字符串是由 s[0] 重复组成。
以上 充分和必要性都证明了，所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
class Solution(object):
def repeatedSubstringPattern(self, s):
"""
:type s: str
:rtype: bool
"""
s1=s+s
s1=s1[1:-1]
if s in s1:
return True
return False
不过这种解法还有一个问题，就是我们最终还是要判断一个字符串（s + s）是否出现过 s 的过程，大家可能直接用contains，find 之类的库函数，却忽略了实现这些函数的时间复杂度（暴力解法是m * n，一般库函数实现为 O(m + n)）。.
KMP
在一个串中查找是否出现过另一个串，这是KMP的看家本领。那么寻找重复子串怎么也涉及到KMP算法了呢？
KMP算法中next数组为什么遇到字符不匹配的时候可以找到上一个匹配过的位置继续匹配，靠的是有计算好的前缀表。
前缀表里，统计了各个位置为终点字符串的最长相同前后缀的长度。
那么 最长相同前后缀和重复子串的关系又有什么关系呢。
可能很多录友又忘了 前缀和后缀的定义，再回顾一下：
- 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
- 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
充分性证明
如果一个字符串s是由重复子串组成，那么 最长相等前后缀不包含的子串一定是字符串s的最小重复子串。
证明： 如果s 是有是有最小重复子串p组成。
即 s = n * p
那么相同前后缀可以是这样：
也可以是这样：
最长的相等前后缀，也就是这样：
这里有录友就想：如果字符串s 是有是有最小重复子串p组成，最长相等前后缀就不能更长一些？ 例如这样：
如果这样的话，因为前后缀要相同，所以 p2 = p1，p3 = p2，如图：
p2 = p1，p3 = p2 即： p1 = p2 = p3
说明 p = p1 * 3。
这样p 就不是最小重复子串了，不符合我们定义的条件。
所以，如果这个字符串s是由重复子串组成，那么最长相等前后缀不包含的子串是字符串s的最小重复子串。
#必要性证明
📝 本文由 deepseek-v4-pro 根据笔记内容自动发布