最长重复子串（Longest Repeated Substring）

我将为您详细讲解最长重复子串问题，这是一个经典的字符串处理问题，可以使用动态规划高效解决。

问题描述

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

示例：

• 输入: "banana"
• 输出: "ana" (在位置1-3和3-5出现)
• 输入: "abcd"
• 输出: "" (没有重复子串)

解题思路

方法一：动态规划解法

状态定义：
定义dp[i][j]为以字符s[i-1]和s[j-1]结尾的最长公共子串的长度。

状态转移方程：

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

边界条件：

• 当i = 0或j = 0时，dp[i][j] = 0

解题步骤：

1. 初始化DP表

   n = len(s)
   dp = [[0] * (n + 1) for _ in range(n + 1)]
   max_len = 0
   end_pos = 0
   

2. 填充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  # 记录结束位置
   

3. 提取结果

   if max_len > 0:
       result = s[end_pos - max_len + 1: end_pos + 1]
   else:
       result = ""
   

完整代码：

def longest_repeated_substring_dp(s):
    n = len(s)
    if n == 0:
        return ""
    
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    max_len = 0
    end_pos = 0
    
    for i in range(1, n + 1):
        for j in range(i + 1, n + 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
            else:
                dp[i][j] = 0
    
    if max_len > 0:
        return s[end_pos - max_len + 1: end_pos + 1]
    else:
        return ""

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

方法二：优化解法（后缀数组）

对于更长的字符串，我们可以使用后缀数组来优化：

解题步骤：

1. 构建后缀数组

   def build_suffix_array(s):
       suffixes = []
       for i in range(len(s)):
           suffixes.append(s[i:])
       suffixes.sort()
       return suffixes
   

2. 计算相邻后缀的最长公共前缀

   def longest_common_prefix(s1, s2):
       min_len = min(len(s1), len(s2))
       for i in range(min_len):
           if s1[i] != s2[i]:
               return i
       return min_len
   

3. 寻找最长重复子串

   def longest_repeated_substring_suffix(s):
       suffixes = []
       for i in range(len(s)):
           suffixes.append((s[i:], i))
       suffixes.sort()
   
       max_len = 0
       start_pos = 0
   
       for i in range(len(suffixes) - 1):
           lcp = longest_common_prefix(suffixes[i][0], suffixes[i+1][0])
           if lcp > max_len:
               max_len = lcp
               start_pos = min(suffixes[i][1], suffixes[i+1][1])
   
       if max_len > 0:
           return s[start_pos:start_pos + max_len]
       else:
           return ""
   

示例演示：

以字符串"banana"为例：

动态规划解法步骤：

1. 初始化6×7的DP表
2. 遍历比较：
   • 比较"b"和"a"：不同 → 0
   • 比较"b"和"n"：不同 → 0
   • ...
   • 比较"a"(i=2)和"a"(j=4)：相同 → dp[1][3]+1=1
   • 比较"a"(i=2)和"a"(j=6)：相同 → dp[1][5]+1=1
   • 比较"n"(i=3)和"n"(j=5)：相同 → dp[2][4]+1=2
   • 比较"a"(i=4)和"a"(j=6)：相同 → dp[3][5]+1=3

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

应用场景：

• DNA序列分析
• 文本压缩算法
• 代码重复检测
• 数据挖掘中的模式发现

这种方法能够高效地找到字符串中最长的重复模式，是生物信息学和文本处理中的重要工具。