Rabin-Karp算法在最长回文子串查找中的应用（基于滚动哈希）

题目描述
给定一个字符串 s，找到其中最长的回文子串。回文串是正着读和反着读都一样的字符串。要求使用 Rabin-Karp 滚动哈希 来优化查找过程，将时间复杂度降至 O(n log n) 或更低。

解题步骤

1. 问题分析

暴力解法需要枚举所有子串（O(n²)），并检查每个子串是否为回文（O(n)），总复杂度为 O(n³)。即使优化检查回文的步骤，也需要 O(n²)。而利用滚动哈希可以快速比较子串及其反转，将检查回文的操作降至 O(1)。

2. 滚动哈希原理

滚动哈希允许在常数时间内计算子串的哈希值。例如，对于字符串 s，定义哈希函数：

H(s[i:j]) = (s[i] * base^(j-i-1) + s[i+1] * base^(j-i-2) + ... + s[j-1]) mod modulus

其中 base 是基数（如 131），modulus 是大质数（如 1e9+7）。通过预处理前缀哈希和幂数组，可以在 O(1) 时间内计算任意子串的哈希值。

3. 回文检查的哈希策略

为了检查子串 s[l:r] 是否为回文，需要比较：

• 正序哈希：H_forward(l, r)
• 逆序哈希：H_backward(l, r)

逆序哈希可以通过反转字符串 s 并预处理其前缀哈希得到。如果两个哈希值相等，则子串是回文（忽略哈希冲突时，可通过双哈希降低冲突概率）。

4. 结合二分查找

最长回文子串的长度具有单调性：如果存在长度为 L 的回文子串，则可能存在更长的回文子串。因此可以二分查找回文长度：

• 设当前尝试的长度为 len。
• 遍历所有起始位置 i，检查子串 s[i:i+len] 是否为回文（用滚动哈希 O(1) 判断）。
• 如果存在回文，则尝试更大的长度；否则减小长度。

二分范围：len ∈ [1, n]，每次检查耗时 O(n)，总复杂度 O(n log n)。

5. 算法步骤

1. 预处理 s 和其反转 s_rev 的前缀哈希数组，以及对应的幂数组。
2. 二分查找最长回文长度 L：
   • 对长度 mid，遍历所有起始位置 i，用滚动哈希检查 s[i:i+mid] 是否回文。
   • 若找到回文，更新结果并尝试 mid+1 到 n；否则尝试 1 到 mid-1。
3. 返回找到的最长回文子串。

6. 示例（s = "babad"）

• 二分过程：
  • len=3 时，发现 "bab" 是回文。
  • 尝试 len=4 无回文，len=5 无回文。
  • 最终最长回文为 "bab" 或 "aba"。

7. 优化与注意事项

• 双哈希：使用两套 (base, modulus) 降低哈希冲突概率。
• 奇偶分开处理：分别二分奇数和偶数长度的回文，避免复杂边界处理。
• 马拉车算法（Manacher）：更优的 O(n) 解法，但本题重点在滚动哈希的应用。

通过上述步骤，我们利用滚动哈希将回文检查的复杂度降为 O(1)，整体复杂度优化至 O(n log n)。