面试题库 › Java 后端 › 最长重复子串(LC1044)

最长重复子串(LC1044)

难度 ★★★在 1 场真实面经中被问到 方向:Java 后端考点:数组与字符串

哪些公司问过

华为1

常见岗位:软件开发(未写技术栈)

答案要点

  1. 长度具有单调性:存在长度 L 的重复子串,必存在 L-1 的
  2. 二分长度 L,用 Rabin-Karp 滚动哈希 O(n) 检查是否有重复
  3. 总时间 O(n log n),用双模哈希或命中后比对降低冲突
  4. 后缀数组加 LCP 取相邻后缀最大值;后缀自动机可 O(n)
  5. 数据规模小时 dp[i][j] 求两后缀公共前缀,O(n²)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题