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

题目描述

给定一个字符串s，找出其中最长的重复子串的长度。"重复子串"指的是在该字符串中至少出现两次（可以有重叠部分，但不能是完全相同的两个子串位置）的子串。

例如：

• 输入："banana"，输出：3（最长重复子串"ana"）
• 输入："abcd"，输出：0（没有重复子串）

解题思路

这个问题可以用动态规划来解决，核心思想是：

• 定义dp[i][j]表示以第i个字符结尾的子串和以第j个字符结尾的子串的最长公共后缀长度
• 通过比较字符的相等性来递推这个长度
• 最终找到所有公共后缀长度中的最大值

详细步骤

步骤1：定义状态

定义二维数组dp[i][j]，表示：

• 以字符串s中第i个字符结尾的子串
• 和以第j个字符结尾的子串
• 的最长公共后缀的长度

注意：这里i和j表示字符在字符串中的位置索引（从0开始）。

步骤2：状态转移方程

对于每个位置对(i,j)，其中i < j：

• 如果s[i] == s[j]（即两个位置的字符相同）：
  • 当i > 0时，dp[i][j] = dp[i-1][j-1] + 1
  • 当i == 0时，dp[i][j] = 1（因为前面没有字符了）
• 如果s[i] != s[j]：
  • dp[i][j] = 0

关键点：我们只考虑i < j的情况，避免同一个子串与自己比较。

步骤3：初始化

• 创建一个大小为n×n的二维数组dp，初始值全为0
• 其中n是字符串s的长度

步骤4：填充dp表

我们按行和列遍历整个dp表：

• 外层循环：j从0到n-1
• 内层循环：i从0到j-1（确保i < j）

对于每个(i,j)对：

• 如果s[i] == s[j]：
  • 如果i > 0：dp[i][j] = dp[i-1][j-1] + 1
  • 如果i == 0：dp[i][j] = 1
• 否则：dp[i][j] = 0

步骤5：寻找结果

在填充dp表的过程中，我们记录遇到的最大值：

• result = max(result, dp[i][j])

这个最大值就是最长重复子串的长度。

举例说明

以字符串"banana"为例：

字符串：b a n a n a
索引： 0 1 2 3 4 5

我们构建dp表的部分关键值：

当j=3（字符'a'）时：

• i=1（字符'a'）：s[1]=='a' == s[3]=='a'，且i>0，dp[1][3] = dp[0][2] + 1 = 0 + 1 = 1
• i=3时跳过（i < j不满足）

当j=4（字符'n'）时：

• i=2（字符'n'）：s[2]=='n' == s[4]=='n'，且i>0，dp[2][4] = dp[1][3] + 1 = 1 + 1 = 2

当j=5（字符'a'）时：

• i=1（字符'a'）：s[1]=='a' == s[5]=='a'，且i>0，dp[1][5] = dp[0][4] + 1 = 0 + 1 = 1
• i=3（字符'a'）：s[3]=='a' == s[5]=='a'，且i>0，dp[3][5] = dp[2][4] + 1 = 2 + 1 = 3

最终找到的最大值是3，对应子串"ana"。

算法复杂度

• 时间复杂度：O(n²)，需要填充n×n的dp表
• 空间复杂度：O(n²)，需要存储整个dp表

代码实现（伪代码）

function longestRepeatingSubstring(s):
    n = length(s)
    dp = 创建n×n的二维数组，初始化为0
    result = 0
    
    for j from 0 to n-1:
        for i from 0 to j-1:
            if s[i] == s[j]:
                if i > 0:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 1
                result = max(result, dp[i][j])
            else:
                dp[i][j] = 0
                
    return result

这个解法通过动态规划巧妙地找到了最长的重复子串，核心在于利用公共后缀长度的递推关系来避免重复计算。