459. 重复的子字符串
3
2026-09-09
思路一：最直观的“切积木法”（暴力枚举）
如果你手里有一根长为n的积木，想看它是不是由几个一模一样的小积木连成的，你会怎么做？
小积木的长度一定能整除总长度：
假设总长度是 6，那最小单位的长度只可能是 1、2、3。
长度不可能是 4 或 5，因为 6 没办法被 4 拼满（4+4=8，溢出了）。
小积木最长也只能是原长的一半（至少得重复 2 次）。
动手切开比一比：拿前k个字符作为“模板子串”，看能不能用它连续拼满原字符串。
以abcabcabc为例（长度9）：
试长度 1：
"a"重复9次→右箭头变成aaaaaaaaa，不对。试长度 2：9不能整除2，直接跳过。
试长度 3：模板是 "abc"。9除以3等于3，重复3次："abc" * 3 = "abcabcabc"，完全对上！返回 True。
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
# 子串长度最多到原长度的一半
for k in range(1, n // 2 + 1):
# 只有能整除才可能是重复构成的
if n % k == 0:
sub = s[:k] # 取前 k 个字符作为积木块
repeat_count = n // k # 算一下需要拼几次
if sub * repeat_count == s:
return True
return False思路二：“旋转串”破案法
想象一个转盘或者一个闭合的圆环。
如果一串字母是由周期性的子串拼成的（比如 abab，周期是 ab）：
你把它的头部拿掉一个周期，拼到尾巴上，它长得跟原来一模一样：
abab把前面的ab挪到后面→还是abab。
如果它不是周期性的（比如aba），你怎么挪，都变不回原样（baa、aab都不等于aba）。
那怎么用代码模拟这种“错位移动”？
把两个相同的串拼在一起：s+s。
非重复串
s = "aba"
拼两份： a b a a b a
砍首尾： _ [b a a b] _
找 aba： 肚子里只有 "baab"，找不到了 -> False重复串
s = "abab"
拼两份： a b a b a b a b
砍首尾： _ [b a b a b a] _
找 abab： 肚子里的下标 1~5 刚好是 "abab" -> Trueclass Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
# 把两份拼在一起，挖去头尾，如果在肚子里还能找到自己，就是有重复
return s in (s + s)[1:-1]思路三：KMP 前缀表（经典解法）
利用 KMP 算法的next数组（最长相等前后缀长度数组）。
假设字符串长度为n，计算其next数组：
若最后一个字符的最长相等前后缀长度
next[n-1] > 0；且
n能够整除重复单元的长度n - next[n-1]（即n (mod{n - next[n-1]) == 0）；则说明该字符串由长度为
n - next[n-1]的子串重复构成。
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
if n <= 1:
return False
# 构建 next 数组（前缀表）
next_arr = [0] * n
j = 0
for i in range(1, n):
while j > 0 and s[i] != s[j]:
j = next_arr[j - 1]
if s[i] == s[j]:
j += 1
next_arr[i] = j
longest_border = next_arr[-1]
# 最长公共前后缀长度大于 0，且剩余长度能被原长度整除
return longest_border > 0 and n % (n - longest_border) == 0