Rabin-Karp 算法在滚动哈希中的应用：重复子串查找

题目描述
给定一个字符串 s，找出其最长重复子串（即出现至少两次的子串）。例如，字符串 "banana" 的最长重复子串是 "ana"（出现两次）。要求时间复杂度尽可能低。

解题思路

1. 暴力法的局限性

   • 枚举所有子串，用哈希表记录出现次数，时间复杂度为 O(n²)，空间复杂度 O(n²)（存储所有子串的哈希值），对于长字符串效率低。
   • 优化方向：避免显式存储所有子串，通过滚动哈希在 O(1) 时间内计算子串哈希值。

2. 滚动哈希原理（Rabin-Karp 核心）

   • 将字符串视为一个进制数（例如 base=26，字母映射为 0-25），计算其哈希值：

\[ H(s[i:j]) = (s[i] \times base^{j-i-1} + s[i+1] \times base^{j-i-2} + ... + s[j-1]) \mod M \]

• 通过前缀和公式快速计算任意子串哈希值：
  设 H[i] 为 s[0:i] 的哈希值，则子串 s[i:j] 的哈希值为：

\[ H[j] - H[i] \times base^{j-i} \mod M \]

• 选择大质数 M 避免哈希冲突（如 10^9+7）。

3. 二分搜索优化
   • 观察：如果存在长度为 L 的重复子串，则一定存在长度 <L 的重复子串；反之，如果不存在长度为 L 的重复子串，则更长的子串也不会重复。
   • 利用二分法确定最大长度 L：
     • 搜索范围：left=1, right=n。
     • 每次取 mid=(left+right+1)/2，检查是否存在长度为 mid 的重复子串。
     • 存在则 left=mid，否则 right=mid-1。

详细步骤

1. 初始化参数

   • base=26, M=10**9+7。
   • 预处理 pow_base[i] 存储 base^i % M，用于快速计算幂。

2. 二分搜索框架

   left, right = 1, len(s)  
   while left < right:  
       mid = (left + right + 1) // 2  
       if has_duplicate(s, mid):  
           left = mid  
       else:  
           right = mid - 1  
   return s[start:start+left]  # 根据实际重复子串位置返回  
   

3. 检查函数 has_duplicate(L)

   • 计算字符串所有长度为 L 的子串的滚动哈希值。
   • 用哈希表记录每个哈希值首次出现的起始索引。
   • 如果同一哈希值再次出现，且子串内容相同（防止哈希冲突），则返回 True。

4. 处理哈希冲突

   • 当两个不同子串哈希值相同时，需直接比较字符串内容确认是否重复。

示例演示（s="banana", L=3）

1. 计算所有长度为 3 的子串哈希值：
   • "ban" → 哈希值 h1
   • "ana" → 哈希值 h2
   • "nan" → 哈希值 h3
   • "ana" → 哈希值 h2（重复出现）
2. 发现 "ana" 重复，确认存在长度为 3 的重复子串。

复杂度分析

• 时间复杂度：O(n log n)，二分搜索 O(log n) 次，每次滚动哈希检查 O(n)。
• 空间复杂度：O(n)，存储哈希表。

总结
通过滚动哈希将子串比较优化为 O(1) 时间，结合二分搜索快速定位最大重复长度，是处理长字符串重复子串问题的经典方法。