哈希算法题目：最长重复子串 题目描述： 给定一个字符串 s ，找出其中最长重复子串的长度。重复子串是指在该字符串中至少出现两次的连续子串，且这两个出现位置不能重叠（若允许重叠需特别说明，本题通常默认不重叠）。例如，字符串 "ababa" 的最长重复子串是 "aba" ，但若要求不重叠，则最长重复子串为 "ab" 或 "ba" ，长度为 2。 解题思路（使用哈希算法 + 二分查找）： 问题分析 ： 暴力枚举所有子串并检查重复性，时间复杂度为 O(n³)，不可行。 优化思路：若存在长度为 L 的重复子串，则一定存在长度小于 L 的重复子串（单调性），因此可通过 二分查找 快速尝试可能的长度。 对于每个候选长度 L ，用 哈希表 存储所有长度为 L 的子串的指纹（如多项式哈希），若发现重复指纹且子串位置不重叠，则说明存在长度为 L 的重复子串。 哈希函数设计 ： 使用 滚动哈希 （Rabin-Karp 算法）快速计算子串哈希值。 选取基数 base （如 131）和模数 mod （如 2^64），预处理字符串前缀哈希值，使得任意子串 s[i:j] 的哈希值可在 O(1) 时间内计算。 二分查找框架 ： 初始化 left = 0 , right = n （n 为字符串长度）。 每次取 mid = (left + right + 1) // 2 ，检查是否存在长度为 mid 的重复子串： 若存在，则 left = mid （尝试更长的长度）； 否则 right = mid - 1 。 检查函数实现 ： 遍历所有长度为 L 的子串，计算其哈希值并存入哈希表（键为哈希值，值为子串起始索引）。 若同一哈希值对应多个索引，检查任意两个索引间距是否 ≥ L （确保不重叠）。 注意哈希冲突：当哈希值相同时，需直接比较子串内容确认是否真重复。 复杂度分析 ： 二分查找次数为 O(log n)，每次检查需 O(n) 时间，整体 O(n log n)。 空间复杂度 O(n) 存储哈希表。 示例（以 s = "ababa" 为例）： 二分尝试 L=3：子串 "aba" 在索引 0 和 2 出现，间距 2 <3（重叠），故不满足不重叠条件。 尝试 L=2：子串 "ab" （索引 0、2）或 "ba" （索引 1、3）均满足不重叠，最终答案为 2。 通过结合二分查找的效率和哈希表的快速查找，此方法在较大数据规模下仍能高效求解。