最长重复子串（动态规划解法）

我将为您详细讲解最长重复子串问题的动态规划解法。这个问题是字符串处理中的经典问题，在文本压缩、生物信息学等领域有重要应用。

问题描述
给定一个字符串s，找到该字符串中最长的重复子串的长度。重复子串是指在原字符串中至少出现两次的连续子串，且这两个出现位置不能重叠。

示例
输入：s = "banana"
输出：3
解释：最长重复子串是"ana"，长度为3

解题思路

步骤1：理解问题本质
最长重复子串问题要求找到在原字符串中出现至少两次的最长连续子串。注意：

• 子串必须是连续的
• 至少出现两次
• 出现位置不能重叠

步骤2：动态规划状态定义
我们定义dp[i][j]表示以第i个字符结尾和以第j个字符结尾的最长公共后缀的长度。

如果s[i-1] == s[j-1]，那么：
dp[i][j] = dp[i-1][j-1] + 1
否则：
dp[i][j] = 0

步骤3：状态转移方程详解
对于i从1到n，j从1到n：

• 如果i == j，dp[i][j] = 0（同一个位置不算重复）
• 如果s[i-1] == s[j-1] 且 i != j：
  dp[i][j] = dp[i-1][j-1] + 1
• 否则：
  dp[i][j] = 0

在计算过程中，我们需要记录最大的dp[i][j]值。

步骤4：算法实现细节

def longestRepeatingSubstring(s: str) -> int:
    n = len(s)
    # 创建DP表，dp[i][j]表示以i和j结尾的最长公共后缀长度
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    max_length = 0
    
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i != j and s[i-1] == s[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                max_length = max(max_length, dp[i][j])
            else:
                dp[i][j] = 0
    
    return max_length

步骤5：具体示例分析
以s = "banana"为例：

初始状态：
dp表全为0

迭代过程：

• i=2, j=1: s[1]='a', s[0]='b'，不相等，dp[2][1]=0
• i=3, j=2: s[2]='n', s[1]='a'，不相等，dp[3][2]=0
• i=4, j=3: s[3]='a', s[2]='n'，不相等，dp[4][3]=0
• i=5, j=4: s[4]='n', s[3]='a'，不相等，dp[5][4]=0
• i=6, j=5: s[5]='a', s[4]='n'，不相等，dp[6][5]=0

关键匹配：

• i=4, j=2: s[3]='a', s[1]='a'，相等，dp[4][2]=dp[3][1]+1=1
• i=5, j=3: s[4]='n', s[2]='n'，相等，dp[5][3]=dp[4][2]+1=2
• i=6, j=4: s[5]='a', s[3]='a'，相等，dp[6][4]=dp[5][3]+1=3

最终找到最长重复子串"ana"，长度为3。

步骤6：复杂度分析

• 时间复杂度：O(n²)，需要填充n×n的DP表
• 空间复杂度：O(n²)，用于存储DP表

步骤7：优化思路
虽然动态规划解法直观易懂，但对于长字符串可能不够高效。可以考虑以下优化：

1. 使用滚动数组将空间复杂度优化到O(n)
2. 使用后缀数组或后缀树可以达到O(n)时间复杂度

步骤8：边界情况处理

• 空字符串：返回0
• 所有字符都相同：返回n-1
• 没有重复子串：返回0

这个动态规划解法虽然时间复杂度较高，但思路清晰，代码简洁，适合理解问题的本质。对于实际应用中的长字符串，可以考虑使用更高效的算法。