最长重复子串（Longest Repeated Substring）

我将为您详细讲解最长重复子串问题的动态规划解法。这个问题是寻找一个字符串中出现至少两次的最长子串（这两个子串可以有重叠）。

问题描述

给定一个字符串s，找到其中最长的重复子串。重复子串是指在字符串中至少出现两次的连续字符序列。

示例：

• 输入："banana"
• 输出："ana"（在位置1-3和3-5出现）
• 输入："abcd"
• 输出：""（没有重复子串）

解题思路

方法一：动态规划解法

我们可以使用动态规划来找到两个子串的最长公共后缀。

状态定义：

• dp[i][j] 表示以第i个字符结尾的子串和以第j个字符结尾的子串的最长公共后缀长度

状态转移方程：

如果 s[i-1] == s[j-1] 且 i ≠ j:
    dp[i][j] = dp[i-1][j-1] + 1
否则:
    dp[i][j] = 0

算法步骤：

1. 初始化一个二维dp数组，大小为(n+1)×(n+1)，全部初始化为0
2. 初始化变量max_len记录最长重复子串长度，end_pos记录结束位置
3. 遍历所有可能的i,j组合（i从1到n，j从1到n）
4. 当字符匹配且不是同一位置时，更新dp值
5. 如果找到更长的重复子串，更新max_len和end_pos
6. 最后根据max_len和end_pos构造结果

代码实现：

def longest_repeated_substring(s):
    n = len(s)
    if n == 0:
        return ""
    
    # 初始化dp表
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    max_len = 0
    end_pos = 0
    
    # 填充dp表
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):  # j从i+1开始，避免比较同一位置
            if s[i - 1] == s[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                
                # 更新最长重复子串信息
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_pos = i - 1  # 当前子串的结束位置
    
    # 构造结果
    if max_len == 0:
        return ""
    
    start_pos = end_pos - max_len + 1
    return s[start_pos:end_pos + 1]

复杂度分析：

• 时间复杂度：O(n²)
• 空间复杂度：O(n²)

方法二：优化空间复杂度

我们可以优化空间复杂度到O(n)：

def longest_repeated_substring_optimized(s):
    n = len(s)
    if n == 0:
        return ""
    
    max_len = 0
    end_pos = 0
    
    # 只保存前一行的dp值
    prev_dp = [0] * (n + 1)
    
    for i in range(1, n + 1):
        curr_dp = [0] * (n + 1)
        for j in range(i + 1, n + 1):
            if s[i - 1] == s[j - 1]:
                curr_dp[j] = prev_dp[j - 1] + 1
                
                if curr_dp[j] > max_len:
                    max_len = curr_dp[j]
                    end_pos = i - 1
        prev_dp = curr_dp
    
    if max_len == 0:
        return ""
    
    return s[end_pos - max_len + 1:end_pos + 1]

详细示例解析

以字符串"banana"为例：

初始状态：

s = "banana"
dp表初始化为全0

逐步计算：

1. i=1, j=2: 'b'≠'a' → dp[1][2]=0
2. i=1, j=3: 'b'≠'n' → dp[1][3]=0
3. ...
4. i=2, j=3: 'a'='a' → dp[2][3]=dp[1][2]+1=1
5. i=3, j=4: 'n'='n' → dp[3][4]=dp[2][3]+1=2
6. i=4, j=5: 'a'='a' → dp[4][5]=dp[3][4]+1=3 ← 找到最长"ana"

最终结果：从位置1到3的"ana"

边界情况处理

1. 空字符串：直接返回空字符串
2. 无重复子串：返回空字符串
3. 全相同字符：返回整个字符串去掉最后一个字符
4. 单个字符：返回空字符串

算法优化思路

对于大规模字符串，还可以使用：

1. 后缀数组：时间复杂度O(n log n)
2. 滚动哈希：使用二分搜索优化

这个动态规划解法虽然时间复杂度较高，但思路清晰，易于理解，适合中等规模的问题。