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

题目描述
给定一个字符串 s，找出其中最长重复子串的长度。重复子串是指在字符串中至少出现两次的连续子串，且这两个子串不能重叠（若允许重叠，问题会更简单，本题通常假设不重叠）。例如，字符串 "banana" 的最长重复子串是 "ana"，长度为 3。

解题思路

1. 暴力法缺陷：直接枚举所有子串，用哈希表记录出现次数，时间复杂度为 O(n²)，对于长字符串效率低下。
2. 二分 + 滚动哈希优化：
   • 利用二分搜索猜测重复子串的长度 L（0 ≤ L ≤ n/2）。
   • 对每个猜测的 L，用滚动哈希（Rabin-Karp算法核心）快速计算所有长度为 L 的子串的哈希值，存入哈希表。
   • 若某个哈希值出现多次，说明存在长度为 L 的重复子串，可尝试更大的 L；否则减小 L。
3. 滚动哈希原理：通过多项式哈希（如基数取 131）和模运算（如取大质数 1e9+7），使得计算相邻子串哈希值的时间为 O(1)。

步骤详解

1. 二分搜索长度范围：

   • 设左边界 left = 0，右边界 right = n/2（因为重复子串最多长 n/2）。
   • 当 left ≤ right 时，取 mid = (left + right) / 2，检查是否存在长度为 mid 的重复子串。

2. 滚动哈希实现：

   • 选择基数 base = 131 和模数 mod = 10^9+7。
   • 预处理字符串的哈希数组 hash[] 和基数幂数组 power[]：

     hash[i] = (hash[i-1] * base + s[i]) % mod
     power[i] = (power[i-1] * base) % mod
     

   • 子串 s[l:r] 的哈希值公式：

     H(l, r) = (hash[r] - hash[l-1] * power[r-l+1]) % mod
     

3. 检查长度 L 的重复子串：

   • 从索引 0 开始，计算每个长度为 L 的子串哈希值，存入哈希表（同时记录子串起始位置）。
   • 若同一哈希值出现多次，且对应子串起始位置之差 ≥ L（确保不重叠），则返回 true。
   • 注意哈希冲突：若哈希值相同但子串实际不同，需直接比较子串内容（本题假设冲突概率低，可忽略）。

4. 调整搜索边界：

   • 若存在长度为 L 的重复子串，则 left = mid + 1，尝试更长的子串。
   • 否则 right = mid - 1，缩短长度。

5. 复杂度分析：

   • 二分搜索 O(log n) 轮，每轮滚动哈希计算 O(n)，总时间复杂度 O(n log n)。
   • 空间复杂度 O(n) 存储哈希表和预处理数组。

示例验证（以 s = "banana" 为例）

• 二分初始：left=0, right=3（n=6）。
• 猜 L=3：计算所有长 3 的子串哈希（"ban", "ana", "nan", "ana"），发现 "ana" 重复且不重叠，记录 ans=3，继续猜更大长度。
• 猜 L=4：无重复子串，终止搜索，最终结果为 3。

通过结合二分法与滚动哈希，高效解决了最长重复子串问题。