01

60 秒回答模板

最长重复子串指在同一个字符串中至少出现两次的连续子串。简单做法是枚举所有子串并比较，复杂度很高。更常见的面试回答是构造所有后缀，排序后最长重复子串一定出现在相邻后缀的最长公共前缀里，取最大 LCP 即可；也可以二分长度，用 rolling hash 判断是否存在重复长度为 L 的子串。后缀数组更系统，哈希实现更快但要处理碰撞。以 ababa 为例，ab 出现两次，长度至少为 2。

考点 后缀相邻
难度 真实面经题
回答目标 讲清方法、边界和追问
02

深入解析

01

定义重复子串

重复子串必须是连续片段，并且在原字符串中出现至少两次。面试要确认重叠是否允许，例如 ababa 中 aba 可以重叠出现。

02

后缀排序思路

把每个位置开始的后缀列出来并排序。两个有长公共前缀的后缀在排序后会相邻，因此最长重复子串可转化为相邻后缀的最大 LCP。

03

哈希二分思路

二分答案长度 L，用 rolling hash 扫描所有长度为 L 的子串，若发现重复哈希且内容确认相同，说明长度 L 可行，再尝试更长。

04

复杂度取舍

后缀数组构建较复杂但确定性强，适合系统讲解；二分加哈希实现相对直接，平均性能好，但要说明哈希碰撞和双哈希校验。

05

输出长度或子串

如果只输出长度，记录最大 LCP 或二分最大可行 L 即可；如果输出子串，还要保存对应起点，并定义多个答案并列时返回哪一个。

javascript

二分长度判断是否存在重复子串

function longestRepeatedSubstringLength(s) {
  let left = 0;
  let right = s.length - 1;
  let answer = 0;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (hasRepeatedLength(s, mid)) {
      answer = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return answer;
}

function hasRepeatedLength(s, len) {
  if (len === 0) return true;
  const seen = new Set();
  for (let i = 0; i + len <= s.length; i += 1) {
    const part = s.slice(i, i + len);
    if (seen.has(part)) return true;
    seen.add(part);
  }
  return false;
}
  • 代码为了表达思路使用切片；大数据版本可把 `hasRepeatedLength` 换成 rolling hash。
  • 示例 `ababa` 中 `ab` 重复出现，若考虑重叠还要按题意确认 `aba` 是否算重复。
03

易错点

  • 不要把最长重复子序列当成最长重复子串，子串必须连续。
  • 不要只给暴力枚举，复杂度通常无法接受。
  • 不要使用哈希时完全不提碰撞风险。
04

面试官追问

重复子串允许重叠吗？

要按题意确认。很多最长重复子串题允许重叠，若不允许，需要额外检查两个起点距离至少为子串长度。

后缀数组为什么只看相邻后缀？

排序后公共前缀相近的后缀会聚在一起，任意两后缀的最长公共前缀会被相邻比较覆盖到最大值。

rolling hash 如何降低碰撞风险？

可以用双模数、64 位哈希加内容回查，最终以真实字符串比较确认重复。