LeetCode 补充题 158. 最长相邻重复子串
题目描述
牛客原题： ✅ 补充题 158. 最长相邻重复子串
重复块定义为某个非空字符串
X连续拼接两次形成的XX。给定字符串
s，返回其中最长重复块的总长度；不存在则返回0。例如，abcabc是长度为6的重复块，两段相同文本之间不能夹其他字符。
示例 1：
输入：
s = "abcabc"
输出：6
解释： 取X="abc"，连续拼接两次得到长度为 6 的重复块。
示例 2：
输入：
s = "abcba"
输出：0
解释： 没有非空字符串连续重复两次的子串。
示例 3：
输入：
s = "aaaaa"
输出：4
解释： 取X="aa"，重复块为"aaaa"；不能将剩余一个a算进重复块。
提示：
- 字符串长度不大于
10^3 - 保证字符串一定由小写字母构成。
题意分析
两次出现必须紧邻且长度相等。若固定半段长度
h，合法起点i就必须满足前一段与向右偏移h的后一段逐字符相等，因此可以按偏移量逐轮检查。
解法：枚举半长并滚动连续匹配数
核心思路
[!blue]
固定
h后，从右向左扫描i，用run表示从i起，s[i...]与s[i+h...]连续相同的长度。若当前两个字符相等，取右侧已有连续长度加 1；否则立即归零。当
run >= h时，区间[i,i+h)与[i+h,i+2h)的每一位都相等，且两者首尾相接，恰好形成长度为2h的重复块。连续匹配长度也保证第二段没有越界。枚举
1 <= h <= n/2覆盖全部可能半长。每轮只需一个计数器，不用保存完整的公共前缀长度表；答案记录两段总长度，不能返回h或整个run。
解题步骤
- 枚举相邻重复块的半段长度h。
- 逆序比较间距为h的两字符，维护连续相等长度。
- 连续相等长度达到h时更新总长度2h。
代码实现
class Solution {
public int longestRepeat(String s) {
int answer = 0;
int n = s.length();
for (int h = 1; h * 2 <= n; h++) {
int run = 0;
for (int i = n - h - 1; i >= 0; i--) {
run = s.charAt(i) == s.charAt(i + h) ? run + 1 : 0;
if (run >= h) {
answer = Math.max(answer, h * 2);
}
}
}
return answer;
}
}
func longestRepeat(s string) int {
answer := 0
for h := 1; h*2 <= len(s); h++ {
run := 0
for i := len(s) - h - 1; i >= 0; i-- {
if s[i] == s[i+h] {
run++
} else {
run = 0
}
if run >= h {
answer = max(answer, h*2)
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n^2)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
run≥h时，起点i的两个相邻长度h区间完全相同，答案可更新为2h；每个h只需要一个计数器，不必建立整张LCP表。
易错点总结
[!yellow]
返回的是2h而不是h；不连续的两次出现不算；向右比较产生的run必须从右到左计算。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 459. 重复的子字符串 | 简单 | 原题判断整个串是否由周期重复构成，本题在任意局部位置寻找恰好相邻的两块。 |
| 1044. 最长重复子串 | 困难 | 原题只需某子串重复出现，本题还要求两次出现紧邻并形成 XX，不能直接套原题结果。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！