Rabin-Karp算法在重复子串查找中的应用

题目描述：给定一个字符串s，找出其中最长重复子串。重复子串是指在字符串中至少出现两次的连续子串。要求算法时间复杂度尽可能高效。

解题过程：

1. 问题分析：

   • 最长重复子串可能有多个，我们只需找到其中一个
   • 暴力解法需要O(n³)时间复杂度（枚举所有子串O(n²)，每个子串在字符串中查找O(n)）
   • 使用Rabin-Karp算法结合二分搜索可以优化到O(n log n)

2. 核心思路：

   • 使用二分搜索来猜测重复子串的长度L
   • 对于每个猜测的长度L，使用滚动哈希在O(n)时间内检查是否存在长度为L的重复子串
   • 通过二分搜索不断调整L的大小

3. 滚动哈希设计：

   • 选择基数base = 26（小写字母）或更大的质数
   • 选择模数mod，避免哈希冲突，通常选择大质数
   • 哈希公式：hash = (hash * base + charCode) % mod

4. 具体步骤：

   • 初始化left = 1, right = n-1（n为字符串长度）
   • 当left ≤ right时：
     a. 计算mid = (left + right) / 2，即当前猜测的子串长度
     b. 检查是否存在长度为mid的重复子串：
     • 计算字符串前mid个字符的哈希值
     • 使用滚动哈希计算所有长度为mid的子串哈希值
     • 将哈希值存入哈希表，记录出现位置
     • 如果发现重复哈希，验证是否为真重复（防止哈希冲突）
       c. 如果存在重复子串，left = mid + 1，否则right = mid - 1

5. 哈希冲突处理：

   • 当发现哈希值重复时，需要实际比较子串内容确认
   • 可以使用双哈希（两个不同的基数和模数）进一步降低冲突概率

6. 复杂度分析：

   • 二分搜索：O(log n)次迭代
   • 每次迭代：O(n)时间计算滚动哈希
   • 总复杂度：O(n log n)

这种方法相比暴力解法有显著效率提升，特别适合处理长字符串。