最长重复子串 题目描述 给定一个字符串 s，找出其中最长的重复子串的长度。重复子串是指在字符串中至少出现两次的连续子串。如果不存在重复子串，返回 0。 解题思路 我们可以使用二分查找结合滚动哈希（Rabin-Karp算法）来解决这个问题。基本思路是： 使用二分查找猜测可能的最大重复子串长度 L。 对于每个猜测的长度 L，使用滚动哈希来高效地计算所有长度为 L 的子串的哈希值。 将哈希值存入哈希集合，如果发现重复的哈希值，说明存在长度为 L 的重复子串。 根据是否存在重复子串，调整二分查找的范围，最终找到最大的 L。 详细步骤 步骤1：二分查找设定搜索范围 重复子串的长度 L 可能的范围是 0 到 n-1（n 为字符串长度）。 初始化 left = 0, right = n。 当 left < right 时，计算 mid = (left + right + 1) // 2。 检查是否存在长度为 mid 的重复子串。 步骤2：滚动哈希计算 为了高效计算子串哈希，我们选择一个基数 base（如 26 或 131）和模数 modulus（如一个大素数，例如 10^9+7）。 预处理字符串的哈希数组和基数幂数组，以便快速计算任意子串的哈希值。 对于长度为 L 的子串，其哈希值可以通过以下公式计算： hash(i, j) = (hash_prefix[j] - hash_prefix[i] * base_power[j-i]) % modulus 其中 hash_ prefix[ k] 是 s[ 0..k] 的哈希值，base_ power[ k ] 是 base^k。 步骤3：检查特定长度 L 是否存在重复子串 初始化一个哈希集合 seen。 遍历字符串，计算每个起始索引 i 对应的长度为 L 的子串的哈希值。 如果当前哈希值已经在集合 seen 中，说明找到了重复子串，返回 True。 否则，将哈希值加入集合。 注意：由于哈希冲突，当发现重复哈希值时，可以进一步验证子串是否确实相同（可选，但推荐）。 步骤4：调整二分查找范围 如果长度为 mid 存在重复子串，则最大长度至少为 mid，将 left 设为 mid。 否则，最大长度小于 mid，将 right 设为 mid - 1。 步骤5：返回结果 二分查找结束后，left 即为最长重复子串的长度。 示例 以字符串 "banana" 为例： 最长重复子串是 "ana"（出现在索引1和3），长度为3。 二分查找过程： L=3时，发现哈希值重复（对应 "ana"），left=3。 继续检查更大长度，L=4、5均无重复，最终确定最大长度为3。 通过结合二分查找和滚动哈希，我们可以在 O(n log n) 时间内高效解决该问题。