最长重复子串（Longest Repeated Substring）

题目描述
给定一个字符串s，找到其中最长的重复子串。重复子串是指在字符串中至少出现两次（出现位置不能重叠）的连续子串。如果有多个这样的子串，返回任意一个即可。

解题过程

这个问题可以用动态规划高效解决。让我们循序渐进地分析：

1. 问题分析

• 我们需要找到在字符串s中出现至少两次的连续子串
• 子串的出现位置不能重叠
• 目标是找到最长的这样的子串

2. 动态规划定义
定义dp[i][j]为以第i个字符和第j个字符结尾的最长公共子串的长度，其中i < j。

3. 状态转移方程

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

4. 边界条件

• 当i = 0或j = 0时，dp[i][j] = 0
• 当i = j时，我们不考虑这种情况，因为同一个位置不能算作重复

5. 算法步骤
让我们通过一个例子来理解：s = "ababc"

步骤1：初始化dp表

   - a b a b c
- 0 0 0 0 0 0
a 0
b 0
a 0  
b 0
c 0

步骤2：填充dp表

• 比较s[0]和s[1]: 'a' ≠ 'b' → dp[1][2] = 0

• 比较s[0]和s[2]: 'a' = 'a' → dp[1][3] = dp[0][2] + 1 = 1

• 比较s[0]和s[3]: 'a' ≠ 'b' → dp[1][4] = 0

• 比较s[0]和s[4]: 'a' ≠ 'c' → dp[1][5] = 0

• 比较s[1]和s[2]: 'b' ≠ 'a' → dp[2][3] = 0

• 比较s[1]和s[3]: 'b' = 'b' → dp[2][4] = dp[1][3] + 1 = 1 + 1 = 2

• 比较s[1]和s[4]: 'b' ≠ 'c' → dp[2][5] = 0

• 比较s[2]和s[3]: 'a' ≠ 'b' → dp[3][4] = 0

• 比较s[2]和s[4]: 'a' ≠ 'c' → dp[3][5] = 0

• 比较s[3]和s[4]: 'b' ≠ 'c' → dp[4][5] = 0

6. 寻找结果
在填充dp表的过程中，我们记录最大值和对应的位置：

• 最大值为2，出现在dp[2][4] = 2
• 这意味着以位置1和位置3结尾有长度为2的重复子串
• 子串是s[1-2+1:1+1] = s[0:2] = "ab"

7. 复杂度分析

• 时间复杂度：O(n²)，其中n是字符串长度
• 空间复杂度：O(n²)

8. 优化
我们可以优化空间复杂度到O(n)，因为每次只需要前一行的信息：

def longest_repeated_substring(s):
    n = len(s)
    max_length = 0
    end_pos = 0
    
    # 使用两行来优化空间
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if s[i-1] == s[j-1]:
                curr[j] = prev[j-1] + 1
                if curr[j] > max_length:
                    max_length = curr[j]
                    end_pos = i - 1
            else:
                curr[j] = 0
        prev, curr = curr, prev
    
    if max_length > 0:
        return s[end_pos - max_length + 1: end_pos + 1]
    return ""

9. 验证
对于s = "ababc"：

• 最长重复子串是"ab"或"ba"
• 算法正确找到了"ab"

这个解法通过动态规划高效地找到了最长的重复子串，既保证了正确性又具有良好的时间复杂度。