Rabin-Karp算法在重复子串查找中的应用 题目描述： 给定一个字符串 s ，找出其中最长重复子串的长度。重复子串是指在字符串中出现至少两次的连续子串（两次出现可以重叠）。例如，字符串 "banana" 的最长重复子串是 "ana"，长度为 3。 解题过程： 问题分析 最直接的方法是枚举所有可能的子串，用哈希表记录每个子串的出现次数，但这样时间复杂度会达到 O(n²)，对于长字符串效率很低。Rabin-Karp 算法通过滚动哈希（Rolling Hash）在 O(n) 时间内计算子串的哈希值，结合二分查找优化，可以将时间复杂度降至 O(n log n)。 滚动哈希原理 滚动哈希的核心是设计一个哈希函数，使得从位置 i 到 i+L-1 的子串哈希值可以通过前一个子串（位置 i-1 到 i+L-2 ）的哈希值快速计算。常用公式为： \[ H(s[ i:i+L]) = (H(s[ i-1:i+L-1]) - s[ i-1] \cdot base^{L-1}) \cdot base + s[ i+L-1 ] \] 其中 base 是一个质数（如 131），通过模运算避免溢出（模数可选一个大质数如 10^9+7）。 二分查找优化 最长重复子串的长度 L 满足单调性：如果存在长度为 L 的重复子串，那么长度小于 L 的子串也一定存在重复。因此可以二分查找可能的长度： 初始化 low=1 , high=n （字符串长度）。 每次取 mid=(low+high+1)//2 ，检查是否存在长度为 mid 的重复子串。 如果存在，说明答案至少为 mid ，继续检查更长的子串（ low=mid ）；否则检查更短的子串（ high=mid-1 ）。 检查固定长度的重复子串 对于当前长度 L ，用滚动哈希计算所有长度为 L 的子串的哈希值，存入哈希表。如果某个哈希值出现两次，说明存在重复子串（需进一步验证避免哈希冲突，但概率较低）。 示例演示（s="banana"） 二分查找： low=1 , high=6 → mid=3 。 检查长度 3 的子串哈希值： "ban"→哈希值 H1, "ana"→H2, "nan"→H3, "ana"→H2（重复出现）。 找到重复子串 "ana"，更新 low=3 。 下一步 mid=5 ，无重复子串，最终结果为 3。 复杂度分析 二分查找次数：O(log n)。 每次检查所有长度为 L 的子串：O(n)。 总复杂度：O(n log n)。 通过结合滚动哈希和二分查找，该算法高效地解决了最长重复子串问题。