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

题目描述：
给定一个字符串 s，判断 s 中是否存在长度至少为 2 的重复子串。如果存在，返回 true；否则返回 false。注意：重复子串可以重叠，例如 "aba" 中 "a" 重复出现，但长度不足 2，因此返回 false；而 "abab" 中 "ab" 重复出现，返回 true。

解题过程：

1. 问题分析
   暴力解法是枚举所有长度 L（从 2 到 n/2）的子串，检查每个长度为 L 的子串是否重复出现，但时间复杂度为 O(n³)。Rabin-Karp 算法通过滚动哈希将时间复杂度优化至 O(n²)。

2. 滚动哈希原理
   将字符串视为一个多进制数（例如基数为 26，假设只含小写字母），计算子串的哈希值。当窗口向右滑动时，新哈希值可通过旧哈希值快速计算：
   新哈希值 = (旧哈希值 - 移除字符的贡献) * 基数 + 新字符的贡献
   为避免溢出，需对一个大素数取模（如 10⁹+7）。

3. 算法步骤

   • 遍历可能的子串长度 L（从 1 到 n/2）：
     • 初始化一个空哈希集合，存储已出现的子串哈希值。
     • 计算前 L 个字符的哈希值 hash_old。
     • 从下标 0 开始滑动长度为 L 的窗口：
       • 若当前 hash_old 已在集合中出现，说明找到重复子串，返回 true。
       • 否则将 hash_old 加入集合。
       • 若窗口未到末尾，计算下一个窗口的哈希值：
         hash_new = (hash_old - s[start] * base^(L-1)) * base + s[start+L]
         注意：需预处理 base^(L-1) 的模幂结果。
   • 若所有 L 均无重复，返回 false。

4. 冲突处理
   哈希可能冲突，因此当哈希值匹配时，需用直接比较子串内容确认是否真重复（避免误判）。

5. 复杂度分析
   外层遍历 L 为 O(n)，内层滑动窗口为 O(n)，整体 O(n²)。空间复杂度 O(n) 存储哈希集合。

示例：s = "abab"

• L=2 时，窗口 "ab" 哈希值加入集合；滑动到 "ba"，哈希值不同；再滑动到 "ab"，哈希值在集合中存在，检查内容后确认重复，返回 true。