字符串简单2 种解法
#459重复的子字符串
判断非空字符串能否由某个更短子串重复若干次构成。
#字符串#字符串匹配#KMP
原题
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba" 输出: false
示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
1 <= s.length <= 104s由小写英文字母组成
解题主线
- 若 s 具有周期，s 一定会出现在 (s + s) 去掉首尾字符后的内部。
- KMP 的最长相等真前后缀长度为 L 时，候选周期为 n - L；它必须整除 n。
解法 1：双倍字符串
在 s+s 中从下标 1 开始找 s；若首次匹配位置小于 n，则存在非平凡旋转周期。
-
时间复杂度： O(n²) 最坏，取决于 String.indexOf 的朴素匹配
-
空间复杂度： O(n)
final class Solution {
public boolean repeatedSubstringPattern(String s) {
// 两份字符串拼接包含所有旋转结果；周期串会在非零偏移处再次出现。
String doubled = s + s;
// 从 1 开始排除原串本身，位置必须小于 n 才是非平凡旋转。
return doubled.indexOf(s, 1) < s.length();
}
}解法 2：KMP 前缀函数
构造每个前缀的最长相等真前后缀长度，用最终边界推导最短周期。
-
时间复杂度： O(n)
-
空间复杂度： O(n)
final class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
int[] prefix = new int[n];
for (int i = 1; i < n; i++) {
// matched 表示 s[0..i-1] 的最长相等真前后缀长度。
int matched = prefix[i - 1];
// 失配时沿前缀链回退，不重复比较已经确认相等的字符。
while (matched > 0 && s.charAt(i) != s.charAt(matched)) {
matched = prefix[matched - 1];
}
if (s.charAt(i) == s.charAt(matched)) matched++;
prefix[i] = matched;
}
int border = prefix[n - 1];
int period = n - border;
return border > 0 && n % period == 0;
}
}边界与易错点
- 不能把完整 s+s 的首个位置 0 当作周期证据。
- 逐个旋转虽然可行，但 O(n²) 且反复复制，已替换为线性 KMP。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
easy/Q459_repeatedSubstringPattern.java