Rabin-Karp算法在重复子串查找中的应用（最长重复子串问题） 题目描述 给定一个字符串 s ，找出其中最长重复子串的长度。重复子串指在字符串中出现至少两次的连续子串（两个子串可以重叠）。例如，字符串 "banana" 的最长重复子串是 "ana" ，长度为 3。 解题过程 问题分析 暴力解法需要枚举所有子串，再通过哈希表检查是否重复出现。但子串数量为 O(n²)，直接存储子串会占用过高内存。 目标：通过哈希算法将子串映射为整数（哈希值），用哈希值快速比较子串是否相同。 滚动哈希原理 将字符串视为一个进制数（如 base=26），将字符映射为数字（a→0, b→1, ...）。 定义哈希函数：对于子串 s[i:j] ，哈希值 H(i, j) = (s[i] * base^(j-i-1) + s[i+1] * base^(j-i-2) + ... + s[j-1]) mod M 其中 M 为一个大素数，避免溢出。 关键优势：通过前一个子串的哈希值，可在 O(1) 时间计算下一个子串的哈希值。例如，从 H(i, j) 计算 H(i+1, j+1) ： H(i+1, j+1) = [ (H(i, j) - s[i] * base^(L-1)) * base + s[j] ] mod M ，其中 L 为子串长度。 二分搜索优化 直接枚举所有长度仍需 O(n²)。利用 二分搜索 ：若存在长度为 L 的重复子串，则一定存在更短的重复子串（如长度 L-1 ）。 搜索范围：长度 L 从 0 到 n-1 ，通过二分快速定位最大有效 L 。 算法步骤 步骤 1：初始化 low=0 , high=n-1 ，记录结果 ans=0 。 步骤 2：当 low ≤ high 时： 取中间长度 mid = (low+high)//2 。 检查是否存在长度为 mid 的重复子串： 计算所有长度为 mid 的子串的滚动哈希值。 将哈希值存入哈希集合，若遇到重复哈希值，说明找到重复子串（需进一步验证避免哈希冲突）。 若存在：更新 ans=mid ，并搜索更长的子串（ low=mid+1 ）。 若不存在：搜索更短的子串（ high=mid-1 ）。 步骤 3：返回 ans 。 避免哈希冲突 当两个不同子串哈希值相同时，需直接比较子串内容确认是否真重复。 优化：使用双哈希（两个不同基数和模数）降低冲突概率。 示例演示 以 s="banana" 为例： 搜索长度 L=3 时，计算所有长度为 3 的子串哈希值： "ban"→H1 , "ana"→H2 , "nan"→H3 , "ana"→H2 。 发现 H2 重复，且子串 "ana" 确实重复，确认存在长度为 3 的重复子串。 复杂度分析 时间复杂度：O(n log n)，二分搜索 O(log n) 轮，每轮计算哈希值 O(n)。 空间复杂度：O(n)，存储哈希集合。 总结 通过滚动哈希将子串比较优化为 O(1) 时间，结合二分搜索快速定位最长重复子串长度，是 Rabin-Karp 算法的典型应用场景。