哈希算法题目：最长重复子串（基于后缀数组与哈希优化）

题目描述
给定一个字符串 s ，请你找出其中最长重复子串的长度。这里的 "重复子串" 指在原字符串中以完全相同的形式出现过至少两次的子串（两个出现位置可以重叠）。如果不存在，则返回 0。

示例

• 输入: s = "banana"
  输出: 3
  解释: 最长重复子串是 "ana"，长度为 3（出现在位置 1 和 3，索引从 0 开始）。
• 输入: s = "abcd"
  输出: 0
  解释: 没有重复出现的子串。

解题思路
最直接的暴力解法是枚举所有子串，并用哈希表记录出现次数，但时间复杂度为 O(n³)（枚举子串 O(n²)，检查哈希 O(n)），不可行。我们需要更高效的方法。结合 后缀数组排序 和 二分查找，并利用 滚动哈希 加速比较，可以将复杂度优化到 O(n log n)。

关键点

• 后缀数组：字符串的所有后缀按字典序排序后，重复子串一定是某些相邻后缀的最长公共前缀（LCP）。
• 二分查找答案：我们可以在可能的长度范围 [0, n] 内二分查找，判断是否存在长度为 L 的重复子串。
• 滚动哈希：用于快速比较子串是否相等，避免逐字符比较。

解题步骤

第一步：理解问题转化
假设最长重复子串的长度为 L，那么：

1. 一定存在两个起始位置 i 和 j（i ≠ j），使得 s[i:i+L] 与 s[j:j+L] 完全相同。
2. 如果我们对所有后缀进行排序，重复子串会使得某些后缀的前 L 个字符相同。
3. 因此问题转化为：寻找最大的 L，使得存在两个后缀，其最长公共前缀长度 ≥ L。

第二步：设计检查函数
给定长度 L，检查是否存在长度为 L 的重复子串：

1. 计算字符串 s 的滚动哈希值，使我们可以 O(1) 时间获取任意子串的哈希值。
2. 遍历所有起始位置 i（0 ≤ i ≤ n-L），计算子串 s[i:i+L] 的哈希值。
3. 将哈希值存入哈希表，如果发现相同的哈希值且两个子串起始位置不同，说明存在重复子串（需二次检查避免哈希冲突）。
   这个方法时间复杂度 O(n)，用于每次检查。

第三步：二分查找框架

• 初始化 left = 0, right = n。
• 当 left < right 时：
  • mid = (left + right + 1) // 2。
  • 调用检查函数 has_duplicate(mid)，如果存在长度为 mid 的重复子串，则 left = mid，否则 right = mid - 1。
• 最终 left 即为最长重复子串长度。

第四步：滚动哈希实现
我们使用双哈希降低冲突概率：

• 选择两个质数 p1 和 p2（如 131 和 13331），以及模数 mod（如 2^64，利用自然溢出）。
• 预处理前缀哈希：
  hash1[i] = hash1[i-1] * p1 + s[i]
  同理计算 hash2。
• 子串哈希计算：
  对于子串 s[l:r]，哈希值为：
  h1 = hash1[r] - hash1[l-1] * p1^(r-l+1)
  类似计算 h2。

第五步：后缀数组优化
上述直接枚举子串的方法在检查时仍需 O(n) 遍历所有起始位置。另一种更优方法是用后缀数组：

1. 构建所有后缀的起始位置数组 suffixes = [0, 1, 2, ..., n-1]。
2. 按后缀字符串排序（可使用倍增法 O(n log n) 或 SA-IS O(n)）。
3. 计算相邻后缀的最长公共前缀长度（LCP），可用 Kasai 算法 O(n) 计算。
4. LCP 数组中的最大值即为最长重复子串长度。
   此方法不需二分查找，但实现复杂。我们结合二分和哈希实现更简单。

第六步：算法实现（二分+滚动哈希）
伪代码：

function longestDupSubstring(s):
    n = len(s)
    base1, base2 = 131, 13331
    mod = 2**64  # 自然溢出
    pre1, pre2 = [0]*(n+1), [0]*(n+1)
    pow1, pow2 = [1]*(n+1), [1]*(n+1)
    for i in range(n):
        pre1[i+1] = pre1[i]*base1 + ord(s[i])
        pre2[i+1] = pre2[i]*base2 + ord(s[i])
        pow1[i+1] = pow1[i]*base1
        pow2[i+1] = pow2[i]*base2

    function getHash(l, r):
        h1 = pre1[r] - pre1[l]*pow1[r-l]
        h2 = pre2[r] - pre2[l]*pow2[r-l]
        return (h1, h2)

    function check(L):
        seen = {}
        for i in range(0, n-L+1):
            h = getHash(i, i+L)
            if h in seen:
                j = seen[h]
                if s[i:i+L] == s[j:j+L]:  # 防止哈希冲突
                    return i  # 返回起始位置
            seen[h] = i
        return -1

    left, right = 0, n
    start = 0
    while left < right:
        mid = (left + right + 1)//2
        pos = check(mid)
        if pos != -1:
            left = mid
            start = pos
        else:
            right = mid - 1
    return s[start:start+left]  # 或返回长度 left

第七步：复杂度分析

• 预处理哈希：O(n)。
• 二分查找：O(log n) 次检查。
• 每次检查：O(n) 枚举子串，哈希计算 O(1)。
• 总复杂度：O(n log n)。空间复杂度 O(n) 存储哈希表。

第八步：边界情况

• 字符串长度 0 或 1：直接返回 0。
• 所有字符相同：如 "aaaa"，最长重复子串长度为 n-1。
• 无重复字符：如 "abcd"，返回 0。

总结
本题通过 二分查找答案 和 滚动哈希 相结合，将寻找最长重复子串的复杂度优化到 O(n log n)，避免了暴力枚举。核心技巧在于利用哈希快速比较子串，并通过二分逐步逼近最大长度。实际实现时需注意哈希冲突的处理（如二次字符串比较）。更优的后缀数组方法可达到 O(n)，但实现较复杂。