最长重复子串（动态规划解法） 题目描述： 给定一个字符串s，找到最长重复子串的长度。重复子串是指在字符串中至少出现两次的连续子串，且这两个子串不能重叠（即它们的起始位置不同）。 解题过程： 这是一个经典的字符串处理问题，我们可以使用动态规划来解决。让我详细解释解决这个问题的思路和步骤。 问题分析： 我们需要找到在字符串s中至少出现两次的连续子串 这两个子串不能重叠（起始位置不同） 目标是找到最长的这样的子串 动态规划定义： 定义dp[ i][ j]表示以第i个字符结尾的子串和以第j个字符结尾的子串的最长公共后缀的长度，其中i < j。 状态转移方程： 如果s[ i] == s[ j ]： dp[ i][ j] = dp[ i-1][ j-1 ] + 1 否则： dp[ i][ j ] = 0 边界条件： 当i = 0或j = 0时，dp[ i][ j ] = 0（因为索引从0开始） 算法步骤： 步骤1：初始化一个二维数组dp，大小为n×n，其中n是字符串长度 步骤2：初始化maxLen = 0来记录最长重复子串的长度 步骤3：遍历所有可能的i和j组合（i < j） 步骤4：对于每个位置对(i, j)： 如果s[ i] == s[ j ]： 如果i == 0，dp[ i][ j ] = 1 否则，dp[ i][ j] = dp[ i-1][ j-1 ] + 1 否则：dp[ i][ j ] = 0 步骤5：更新maxLen = max(maxLen, dp[ i][ j ]) 步骤6：返回maxLen 详细示例： 以字符串"ababc"为例： s = "ababc"，n = 5 我们构建dp表： i\j | 0 | 1 | 2 | 3 | 4 --- | -- | -- | -- | -- | -- 0 | 0 | 0 | 1 | 0 | 0 1 | 0 | 0 | 0 | 2 | 0 2 | 0 | 0 | 0 | 0 | 3 3 | 0 | 0 | 0 | 0 | 0 4 | 0 | 0 | 0 | 0 | 0 关键计算： dp[ 0][ 2]：s[ 0]='a'=s[ 2]='a'，所以dp[ 0][ 2 ]=1 dp[ 1][ 3]：s[ 1]='b'=s[ 3]='b'，且dp[ 0][ 2]=1，所以dp[ 1][ 3 ]=2 dp[ 2][ 4]：s[ 2]='a'=s[ 4]='a'，但dp[ 1][ 3]=2，所以dp[ 2][ 4 ]=3 最长重复子串长度是3，对应子串"aba"和"aba"。 时间复杂度优化： 时间复杂度：O(n²) 空间复杂度：O(n²)，可以优化到O(n) 空间优化版本： 我们可以只保存前一行的信息，将空间复杂度从O(n²)降到O(n)。 这个解法通过动态规划巧妙地找到了最长的重复子串，核心思想是利用后缀匹配来识别重复出现的模式。