最长重复子串问题

问题描述
给定一个字符串 s ，找出其中最长的重复子串（即出现至少两次的子串）。若有多个结果，返回任意一个。重复子串要求在原字符串中起始位置不同，但子串内容完全相同。
示例：

• 输入："banana"
• 输出："ana"（或 "na"，但最长长度为 3）

解题思路

1. 暴力枚举所有子串，用哈希表记录出现次数，但时间复杂度为 O(n³)，不可取。
2. 优化思路：二分查找 + 字符串哈希 或 后缀数组。
   • 核心观察：如果存在长度为 L 的重复子串，那么一定存在长度小于 L 的重复子串；反之，如果不存在长度为 L 的重复子串，更长的也不会存在。因此 长度 L 具有单调性，可用二分查找确定最长长度。
   • 对每个长度 L，检查字符串中是否有两个相同子串，可用滚动哈希（Rabin-Karp）快速判断。

步骤详解

步骤1：二分查找最长长度

• 设可能的最长重复子串长度为 [1, n-1]。
• 二分查找：left = 1, right = n-1，每次取 mid = (left+right+1)//2，检查是否存在长度为 mid 的重复子串。
• 若存在，则说明可能更长，移动 left = mid；否则移动 right = mid-1。

步骤2：检查长度为 L 的重复子串是否存在

• 使用滚动哈希（Rabin-Karp）计算所有长度为 L 的子串的哈希值，并用哈希表记录每个哈希值首次出现的起始位置。
• 如果同一个哈希值再次出现，还需检查是否真的一致（防止哈希冲突），若相同则找到重复子串。
• 若存在重复，返回 True 及任意一个子串。

步骤3：滚动哈希设计

• 取模大素数（如 10^9+7 或 2^64 自然溢出），基数常用 26 或 131。
• 递推公式：

  hash(i+1, i+L) = (hash(i, i+L-1) - s[i]*base^(L-1)) * base + s[i+L]
  

  需预处理 base^L 的幂。

步骤4：处理哈希冲突

• 当两个子串哈希值相同时，再进行一次逐字符比较确认。
• 或使用双哈希（两个不同模数）降低冲突概率。

代码实现（Python）

def longestDupSubstring(s: str) -> str:
    n = len(s)
    base = 131
    mod = 10**9 + 7
    nums = [ord(c) for c in s]
    
    # 预处理 base 的幂
    pow_base = [1] * (n+1)
    for i in range(1, n+1):
        pow_base[i] = (pow_base[i-1] * base) % mod
    
    # 检查长度为 L 的子串是否重复
    def check(L):
        seen = {}
        h = 0
        # 计算第一个长度为 L 的子串哈希
        for i in range(L):
            h = (h * base + nums[i]) % mod
        seen[h] = 0
        # 滚动计算后续子串哈希
        for i in range(1, n - L + 1):
            h = (h * base - nums[i-1] * pow_base[L] + nums[i+L-1]) % mod
            h = (h + mod) % mod
            if h in seen:
                # 检查实际字符串是否相同（防止冲突）
                if s[seen[h]:seen[h]+L] == s[i:i+L]:
                    return i
            seen[h] = i
        return -1
    
    # 二分查找最大长度
    left, right = 1, n-1
    res_start = 0
    while left <= right:
        mid = (left + right + 1) // 2
        pos = check(mid)
        if pos != -1:
            res_start = pos
            left = mid + 1
        else:
            right = mid - 1
    return s[res_start:res_start+right]

复杂度分析

• 二分查找次数：O(log n)
• 每次检查 O(n) 个子串，哈希计算 O(1)，总复杂度 O(n log n)
• 空间复杂度 O(n) 存储哈希表

优化与扩展

• 若要求 O(n) 时间，可用后缀数组 + 高度数组（LCP）在 O(n) 内找到最大 LCP 值，对应最长重复子串。
• 该问题在 DNA 序列分析、代码查重等领域有实际应用。