459. 重复的子字符串
题目描述
输入一个非空字符串 s。
判断能否找到 s 的某个子串，把它首尾相接拼两次或更多次后恰好得到 s。
能做到返回 true，否则返回 false。
示例 1
输入：s = "abab" 输出：true
解释："ab" 拼两次即可。
示例 2
输入：s = "aba" 输出：false
解释：找不到满足条件的子串。
示例 3
输入：s = "abcabcabcabc" 输出：true
解释："abc" 拼四次，或 "abcabc" 拼两次。
数据范围
1 <= s.length <= 10^4s只含小写英文字母。
解题思路：枚举子串长度
若 s 由长度为 L 的块重复构成，则 L 必须整除 n 且 L ≤ n / 2，并且对所有 i ≥ L 都有 s[i] == s[i − L]（每个字符等于它左边距离 L 的字符）。依次枚举这样的 L 并逐位校验，任一 L 通过就返回 true。
为什么正确
校验到下标 i 时，s[0..i] 已经是长度 L 的块的重复（最后一块可能不完整）。
复杂度分析
时间 O(n · d(n))，d(n) 为 n 的因数个数；空间 O(1)。
易错点
L 的上界是 n // 2 而不是 n：块至少要重复两次，否则 L = n 总会通过。另一种写法是判断 s 是否出现在 (s + s)[1:-1] 中。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
for L in range(1, n // 2 + 1):
if n % L != 0:
continue
ok = True
for i in range(L, n):
if s[i] != s[i - L]:
ok = False
break
if ok:
return True
return Falseclass Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
for (int L = 1; L <= n / 2; L++) {
if (n % L != 0) {
continue;
}
boolean ok = true;
for (int i = L; i < n; i++) {
if (s.charAt(i) != s.charAt(i - L)) {
ok = false;
break;
}
}
if (ok) {
return true;
}
}
return false;
}
}class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int L = 1; L <= n / 2; L++) {
if (n % L != 0) {
continue;
}
bool ok = true;
for (int i = L; i < n; i++) {
if (s[i] != s[i - L]) {
ok = false;
break;
}
}
if (ok) {
return true;
}
}
return false;
}
};func repeatedSubstringPattern(s string) bool {
n := len(s)
for L := 1; L <= n/2; L++ {
if n%L != 0 {
continue
}
ok := true
for i := L; i < n; i++ {
if s[i] != s[i-L] {
ok = false
break
}
}
if ok {
return true
}
}
return false
}var repeatedSubstringPattern = function(s) {
const n = s.length;
for (let L = 1; L <= n >> 1; L++) {
if (n % L !== 0) {
continue;
}
let ok = true;
for (let i = L; i < n; i++) {
if (s[i] !== s[i - L]) {
ok = false;
break;
}
}
if (ok) {
return true;
}
}
return false;
};function repeatedSubstringPattern(s: string): boolean {
const n = s.length;
for (let L = 1; L <= n >> 1; L++) {
if (n % L !== 0) {
continue;
}
let ok = true;
for (let i = L; i < n; i++) {
if (s[i] !== s[i - L]) {
ok = false;
break;
}
}
if (ok) {
return true;
}
}
return false;
}其他解法
枚举长度直接检查每个候选周期，好写；KMP 用前缀函数一步得到最小周期，复杂度降为 O(n)。
解法 2：KMP 前缀函数 时间 O(n)，空间 O(n)
计算前缀函数 pi，pi[n−1] = L 是整个串最长的相等真前缀和真后缀的长度，于是 n − L 是 s 的最小周期。若 L > 0 且 n − L 能整除 n，s 就由长度为 n − L 的子串重复构成。等价的直观说法是：s 在 s+s 去掉首尾字符后的串中出现。
线性时间，最坏情况也有保证。需要先掌握 KMP 前缀函数和“最小周期 = n − pi[n−1]”这条性质。
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
# pi[i]：s[0..i] 最长的相等真前缀与真后缀的长度
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
L = pi[n - 1]
# 最小周期为 n - L，它整除 n 且不等于 n 时 s 可由子串重复构成
return L > 0 and n % (n - L) == 0class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
int[] pi = new int[n];
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s.charAt(i) != s.charAt(j)) j = pi[j - 1];
if (s.charAt(i) == s.charAt(j)) j++;
pi[i] = j;
}
int L = pi[n - 1];
return L > 0 && n % (n - L) == 0;
}
}class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
int L = pi[n - 1];
return L > 0 && n % (n - L) == 0;
}
};func repeatedSubstringPattern(s string) bool {
n := len(s)
pi := make([]int, n)
for i := 1; i < n; i++ {
j := pi[i-1]
for j > 0 && s[i] != s[j] {
j = pi[j-1]
}
if s[i] == s[j] {
j++
}
pi[i] = j
}
L := pi[n-1]
return L > 0 && n%(n-L) == 0
}var repeatedSubstringPattern = function(s) {
const n = s.length;
const pi = new Array(n).fill(0);
for (let i = 1; i < n; i++) {
let j = pi[i - 1];
while (j > 0 && s[i] !== s[j]) j = pi[j - 1];
if (s[i] === s[j]) j++;
pi[i] = j;
}
const L = pi[n - 1];
return L > 0 && n % (n - L) === 0;
};function repeatedSubstringPattern(s: string): boolean {
const n = s.length;
const pi: number[] = new Array(n).fill(0);
for (let i = 1; i < n; i++) {
let j = pi[i - 1];
while (j > 0 && s[i] !== s[j]) j = pi[j - 1];
if (s[i] === s[j]) j++;
pi[i] = j;
}
const L = pi[n - 1];
return L > 0 && n % (n - L) === 0;
}