滚动哈希在最长回文子串查找中的应用（Rabin-Karp思想扩展） 题目描述 给定一个字符串 s ，要求找到其中最长的回文子串。例如，对于输入"babad"，最长回文子串可能是"bab"或"aba"。要求设计一个基于滚动哈希的算法，在O(n log n)时间内解决该问题。 解题过程 问题分析 最长回文子串问题传统解法有动态规划（O(n²)）或中心扩展法（O(n²)）。 利用滚动哈希（Rabin-Karp思想）可以结合二分搜索，将时间复杂度优化到O(n log n)。 核心思路：对可能的回文长度进行二分搜索，用滚动哈希快速验证是否存在该长度的回文子串。 滚动哈希设计 定义两个哈希函数： 正向哈希（从左到右）： H_forward(i) = (s[0] * base^(i) + s[1] * base^(i-1) + ... + s[i]) mod mod 反向哈希（从右到左）： H_backward(i) = (s[n-1] * base^(i) + s[n-2] * base^(i-1) + ... + s[n-1-i]) mod mod 选择基数 base 和大质数 mod 以减少碰撞（如base=131, mod=10^9+7）。 预处理字符串的正向和反向哈希数组，并计算基数幂次数组 pow_base[] ，便于快速计算子串哈希。 二分搜索回文长度 搜索范围：左边界 left=1 ，右边界 right=n （n为字符串长度）。 每次取中间长度 mid=(left+right+1)/2 ，检查是否存在长度为 mid 的回文子串： 遍历所有起始位置 i （0 ≤ i ≤ n-mid），计算子串 s[i:i+mid] 的正向哈希。 计算对应反向子串的哈希（即 s[i:i+mid] 的反向表示）。 若两个哈希值相等，则说明找到长度为 mid 的回文子串，将左边界移到 mid ；否则将右边界移到 mid-1 。 哈希比较的细节 子串正向哈希： hash_forward = (H_forward[i+mid-1] - H_forward[i-1] * pow_base[mid]) mod mod （需处理i=0时的边界情况，下同） 子串反向哈希： 反向子串对应原字符串的区间为 s[i:i+mid] ，其反向哈希需通过反向哈希数组计算： hash_backward = (H_backward[n-1-i] - H_backward[n-1-i-mid] * pow_base[mid]) mod mod 若 hash_forward == hash_backward ，则子串可能是回文（需进一步检查哈希碰撞，但概率极低）。 复杂度分析 二分搜索次数：O(log n) 每次检查所有长度为 mid 的子串：O(n) 总复杂度：O(n log n) 空间复杂度：O(n)（存储哈希数组和幂次数组） 示例演示（s="babad"） 步骤1：初始化哈希数组和 pow_base[] 。 步骤2：二分搜索最长回文长度。 第一次mid=3：检查所有长度为3的子串，发现"bab"和"aba"的哈希匹配，更新左边界。 后续搜索最终确认最长回文长度为3。 步骤3：记录实际回文子串的起始位置。 关键点 滚动哈希允许在O(1)时间内计算任意子串哈希，避免重复计算。 反向哈希的设计是匹配回文对称性的核心。 二分搜索将问题转化为可快速验证的判定问题。