最长重复子串（Longest Repeated Substring）问题

题目描述

给定一个字符串 S，找到其中出现至少两次（无重叠）的最长子串的长度（或子串本身）。这里的“重复”通常定义为在字符串中出现至少两次的子串（两次出现允许重叠，除非特别限制为不重叠，但经典问题中通常允许重叠）。例如：

• 对于字符串 "banana"，最长重复子串是 "ana"（出现在索引1-3和3-5，重叠）。
• 对于字符串 "abcd"，没有重复子串，结果为空或0。

这是一个经典问题，常用于生物信息学（如DNA序列分析）和文本处理中，有多种解法，包括动态规划、后缀数组、后缀树等。

解题过程

步骤1：基础理解与暴力解法

核心思路：

• 重复子串必须至少出现两次，且可以是任意位置。
• 暴力方法：枚举所有可能的子串起点和长度，检查它是否在字符串中再次出现。

暴力法伪代码：

最长长度 = 0
对于 i 从 0 到 n-1：
    对于 j 从 i+1 到 n-1：
        长度 = 0
        当 i+长度 < n 且 j+长度 < n 且 S[i+长度] == S[j+长度]：
            长度 += 1
        更新最长长度 = max(最长长度, 长度)

时间复杂度：O(n³)（枚举i、j和逐字符比较）。效率极低，需要优化。

步骤2：动态规划解法

核心思路：

• 定义 dp[i][j] 表示以 S[i] 和 S[j] 结尾的最长公共后缀的长度（i != j）。
• 如果 S[i] == S[j]，则 dp[i][j] = dp[i-1][j-1] + 1，否则 dp[i][j] = 0。
• 最终答案是所有 dp[i][j] 中的最大值。

状态转移方程：

如果 S[i] == S[j] 且 i != j：
    dp[i][j] = dp[i-1][j-1] + 1
否则：
    dp[i][j] = 0
最长长度 = max(dp[i][j]) 对所有 i, j

示例（S = "banana"）：

• 比较 b 和 a：不同 -> 0。
• 比较 a（索引1）和 a（索引3）：相同，看前一对（索引0的b和索引2的n）不同 -> 0，所以 dp[1][3] = 0+1=1。
• 但最长在 "ana"：比较 a（索引3）和 a（索引5）：相同，看前一对（索引2的n和索引4的n）相同 -> dp[2][4]=1，再往前（索引1的a和索引3的a）相同 -> dp[1][3]=1，所以 dp[3][5] = 1+1+1=3。

复杂度：时间 O(n²)，空间 O(n²)（可优化到 O(n) 只保留上一行）。但 n 很大时仍效率不足。

步骤3：后缀数组法（高效解法）

核心思路：

• 将字符串的所有后缀排序，重复子串一定是某些后缀的公共前缀。
• 排序后，相邻后缀的最长公共前缀（LCP）中最大的，就对应原串的最长重复子串。

步骤：

1. 生成所有后缀：S 从位置 i 到末尾的子串，i=0..n-1。
2. 对这些后缀按字典序排序。
3. 计算相邻后缀的最长公共前缀长度。
4. 取所有 LCP 的最大值。

示例（S = "banana"）：

• 后缀：0:banana, 1:anana, 2:nana, 3:ana, 4:na, 5:a
• 排序后：5:a, 3:ana, 1:anana, 0:banana, 4:na, 2:nana
• 相邻 LCP：
  • a 和 ana：LCP="a" 长度1
  • ana 和 anana：LCP="ana" 长度3
  • anana 和 banana：LCP="" 长度0
  • banana 和 na：LCP="" 长度0
  • na 和 nana：LCP="na" 长度2
• 最大值是3，对应子串 "ana"。

复杂度：排序后缀需 O(n log n) 比较，每次比较 O(n) 则总 O(n² log n)，但用倍增法+基数排序可优化到 O(n log n) 或 O(n)。这是常用高效方法。

步骤4：后缀树法（最优理论解法）

核心思路：

• 后缀树能存储所有后缀，树中深度最大的内部节点对应的路径即为最长重复子串。
• 构建后缀树可用 Ukkonen 算法在 O(n) 时间完成。

过程：

1. 为 S 构建后缀树。
2. 遍历树，找到最深（字符串长度最长）的内部节点（有至少两个子节点）。
3. 从根到该节点的路径标记即最长重复子串。

示例（S="banana"）的后缀树中，节点对应 "a"、"na" 等，最深内部节点是 "ana"。

复杂度：构建 O(n)，查询 O(n)，空间 O(n)。最优但实现复杂。

步骤5：允许/禁止重叠的处理

• 允许重叠：上述方法默认允许，因为 LCP 可能来自重叠后缀（如索引1和3的 "ana"）。
• 禁止重叠：需额外检查，确保两次出现起始位置距离 >= 子串长度。可在后缀数组法中筛选 LCP 时加入条件。

总结

• 暴力法：O(n³)，仅用于理解。
• 动态规划：O(n²)，中等规模可用。
• 后缀数组：O(n log n) 或 O(n)，实际常用，需掌握 LCP 数组计算。
• 后缀树：O(n) 最优，但实现复杂。

关键点：最长重复子串问题本质是找所有后缀的最长公共前缀，后缀数组平衡了效率与实现难度，是面试中最可能考察的解法。