LeetCode 459. 重复的子字符串
题目描述
题意分析
判断一个非空字符串能否由某个更短的非空字符串连续重复至少两次组成。重复块必须完全相同，并且恰好铺满整个字符串，不能留下未匹配的尾部。
需要寻找的是整个字符串的重复结构，不是某段内容出现过两次，也不是某个前缀与后缀相同即可。若重复块长度为
p、原串长度为n，必须满足p < n，而且n能被p整除。
解法一：拼接字符串去首尾判断
核心思路
[!blue]
把字符串首部的一段移到末尾，称为一次循环位移。若原串由相同短串重复而成，移动一个完整重复块后，得到的字符串仍与原串相同。因此，可以把寻找重复块转化为：是否存在长度介于
1和n - 1之间的循环位移，使原串保持不变。拼接
s + s后，从下标p开始取连续n个字符，恰好就是左移p位后的字符串。下标0和n都是原串本身，无论是否重复都会匹配，所以必须排除。去掉拼接串的首尾各一个字符后，能够容纳完整匹配的起点恰好只剩1..n-1。反过来，若某个非零位移
p后仍与原串相同，就有s[i] == s[(i + p) % n]。反复移动p位，会把下标按gcd(n, p)个余数类连接起来，同一类的字符必须相同。因此原串由长度为gcd(n, p)的块重复组成；这个长度小于n且整除n，满足题目要求。所以只需在裁掉首尾的拼接串中查找原串，存在匹配就返回
true。这里删除的是整个拼接串的两个端点，用来排除两次原位匹配，不是删除原串中的某个重复块。
解题步骤
- 令
doubled = s + s，得到长度为2n的字符串。- 保留区间
[1, 2n - 1)，去掉首尾两个字符。- 在保留的部分中查找完整的
s；能够找到就返回true，否则返回false。- 单字符输入裁剪后为空，不可能包含原串，会自然返回
false。
代码实现
class Solution {
public boolean repeatedSubstringPattern(String s) {
String doubled = s + s;
// 去掉首尾两个原串对齐位置，只检查是否存在非平凡的周期对齐。
return doubled.substring(1, doubled.length() - 1).contains(s);
}
}
import "strings"
func repeatedSubstringPattern(s string) bool {
doubled := s + s
// 去掉首尾两个原串对齐位置，只检查是否存在非平凡的周期对齐。
return strings.Contains(doubled[1:len(doubled)-1], s)
}
复杂度分析
- 时间复杂度：拼接和裁剪需要
O(n)；查找部分取决于标准库实现，采用朴素匹配时最坏为O(n²)。若要求明确的线性最坏上界，可使用下面的 KMP 解法。- 空间复杂度：
O(n)，用于保存拼接后的字符串及可能产生的裁剪副本。
关键点总结
[!green]
- 完整重复等价于存在一次非零、非整串长度的循环位移，使字符串不变。
- 拼接展开循环位移，裁掉首尾排除必然存在的原位匹配。
- 调用标准库让实现简短，但复杂度应把字符串构造和实际匹配过程分别说明。
解法二：KMP 前缀函数
核心思路
[!blue]
定义
pi[i]为前缀s[0..i]的最长相等真前缀与后缀的长度。“真”表示不能取整个前缀本身，这样记录的才是两端之间的有效重合。计算
pi[i]时，先令j = pi[i - 1]。此前已有长度为j的前后缀相等，若当前字符s[i]与s[j]相同，就能把这段重合延长一位。失配时不能直接抛弃所有重合：更短的候选必然也是当前长度为j的前缀的相等前后缀，因此令j = pi[j - 1]继续尝试，直到匹配或退到零。对完整字符串，设最长重合长度为
L = pi[n - 1]，令p = n - L。前后缀相等意味着s[p..n)与s[0..n-p)相同，即每个下标不小于p的字符都等于前移p位的字符。因此p是一个周期；重合越长，周期越短，最长重合对应最短周期。周期只说明字符沿固定距离重复，不保证末尾恰好结束一个完整块。必须再检查
n % p == 0，才能由前p个字符完整铺满全串；同时需要L > 0，排除p == n、只使用整串一次的情况。最终判定是L > 0 && n % p == 0。
解题步骤
- 创建长度为
n的前缀函数数组pi，其中pi[0] = 0。- 从
i = 1开始，先令j = pi[i - 1]，尝试延长上一位置的最长重合。- 当
j > 0且s[i] != s[j]时，反复令j = pi[j - 1]，寻找较短候选。- 如果当前字符能够匹配，将
j加一；再令pi[i] = j。- 取
border = pi[n - 1]、period = n - border，判断是否有非空重合且周期整除总长度。
代码实现
class 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 border = pi[n - 1];
int period = n - border;
// 既要有非空公共边界，又要被候选周期长度整除，才能重复至少两次。
return border > 0 && n % period == 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
}
border := pi[n-1]
period := n - border
// 既要有非空公共边界，又要被候选周期长度整除，才能重复至少两次。
return border > 0 && n%period == 0
}
复杂度分析
- 时间复杂度：
O(n)。匹配长度j每轮至多增加一，失配回退会严格减小它，总回退次数不会超过此前的总增长量。- 空间复杂度：
O(n)，用于前缀函数数组。
关键点总结
[!green]
pi记录长度；j同时是已匹配长度和下一次要比较的前缀下标。- 回退到
pi[j - 1]复用的是已知的前后缀关系，不需要从头重新比较。- 最长相等前后缀给出最短周期，非空和整除条件共同保证至少重复两次且没有残缺尾块。
易错点总结
[!yellow]
- 直接在
s + s中查找：原串一定在下标零处出现，无法区分是否真正重复。- 只裁掉一个端点：另一端仍保留一份完整原串，首尾两次原位匹配都需要排除。
- 只判断存在相等前后缀：它只能说明具有周期，末尾仍可能是不完整的重复块，需要检查整除。
- 忘记
border > 0：没有重合时period == n也能整除总长度，但不满足至少重复两次。- KMP 失配只回退一次：新候选仍可能失配，应使用循环继续沿前缀函数回退。
- 混用长度与下标：下一次比较的是
s[j]，更短边界取自pi[j - 1]，不能交换二者。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 28. 找出字符串中第一个匹配项的下标 | 简单 | KMP前缀函数可复用，本题用最长相同前后缀推断周期，而非定位模式首次出现。 |
| 686. 重复叠加字符串匹配 | 中等 | 同样涉及字符串重复，原题重复源串直到包含目标，本题要求整串恰好由同一短串重复组成。 |
| 214. 最短回文串 | 困难 | 通过字符与模式前缀的匹配状态避免重复比较；本题利用前缀函数判断重复周期，该题将回文前缀转为正反串匹配。 |