哈希算法题目：最长回文子串

字数 3292 2025-12-22 22:47:19

哈希算法题目：最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。
回文串是一个正着读和反着读都一样的字符串。例如，"babad" 的最长回文子串可以是 "bab" 或 "aba"；"cbbd" 的最长回文子串是 "bb"。

这道题通常有多种解法，如动态规划、中心扩展算法等。我们将重点讲解一种利用哈希算法的巧妙方法，它基于字符串哈希和二分查找，可以在平均 O(n log n) 时间内解决，并且空间复杂度为 O(n)。这种方法的核心思想是，如果我们能快速判断一个子串是否是回文，那么就可以通过长度来二分搜索可能的最长回文长度。

解题思路与步骤

我们不会使用暴力枚举所有子串（O(n²) 个子串，每个检查 O(n)，总计 O(n³) 太慢）。而是采用以下步骤：

预处理字符串哈希：计算字符串 s 的前缀哈希和后缀哈希。这允许我们在 O(1) 时间内计算任意子串的正向哈希值和反向哈希值。
利用二分查找确定最长回文长度：对于一个给定的长度 L，我们可以用 O(n) 时间检查 s 中是否存在长度为 L 的回文子串。由于回文长度满足单调性（如果存在长度为 L 的回文，那么一定存在长度 ≤ L 的回文），我们可以对可能的长度进行二分查找。
检查固定长度的回文：对于给定的长度 L，我们滑动一个长度为 L 的窗口遍历字符串。对每个窗口内的子串，用预处理好的哈希值在 O(1) 时间内判断其正向和反向哈希是否相等（需注意处理冲突，但通常双哈希可解决）。如果相等，则该子串是回文，记录其起始位置。
整合结果：二分查找结束后，我们就找到了最长回文子串的长度，同时也知道了一个（或多个）起始位置，从而可以输出这个子串。

详细讲解

步骤 1：字符串哈希的基础

我们选择一种常见的滚动哈希方法：将字符串看作一个某进制（比如基数 base = 131 或 13331，通常选质数）的数，然后对一个较大的质数（如 mod = 10^9 + 7）取模。为了避免哈希冲突，实际中常使用双哈希，即用两个不同的基数和模数计算两套哈希值，只有当两套哈希值都相等时才认为字符串相等，这能极大降低冲突概率。

定义：

设字符串 s 的长度为 n，下标从 1 开始（方便计算）。
pre1[i] 表示 s[1..i] 的前缀哈希值（使用第一套哈希参数）。
pow1[i] 表示 base1^i % mod1，用于快速计算任意子串的哈希。

递推公式：
pre1[i] = (pre1[i-1] * base1 + s[i]) % mod1
pow1[i] = (pow1[i-1] * base1) % mod1

计算子串 s[l..r] 的哈希值：
hash1(l, r) = (pre1[r] - pre1[l-1] * pow1[r-l+1] % mod1 + mod1) % mod1

同理，我们计算后缀哈希 suf1[i] 表示 s[i..n] 的哈希值，但为了判断回文更方便，我们通常直接计算反向字符串的前缀哈希。设 s' 为 s 的反转字符串，计算 s' 的前缀哈希 pre1'。这样，原串 s[l..r] 的反向串就是 s'[n-r+1..n-l+1]，其哈希值可以用 pre1' 快速算出。

步骤 2：二分查找框架

最长回文子串的长度 ansLen 一定在 0 到 n 之间。我们可以二分查找这个长度。

初始化 left = 1, right = n, ansStart = 0。
当 left <= right 时：
1. 取候选长度 mid = (left + right) / 2。
2. 调用函数 check(mid)，检查是否存在长度为 mid 的回文子串。如果存在，返回一个起始位置 pos（或 true 并记录位置），否则返回 -1。
3. 如果 check(mid) 找到了回文（返回的位置不是 -1），则更新 ansLen = mid, ansStart = pos，并尝试更长的长度，即 left = mid + 1。
4. 否则，说明当前长度 mid 不存在回文，尝试更短的长度，即 right = mid - 1。
二分结束后，ansStart 是某个最长回文子串的起始位置（0-indexed 或 1-indexed 需一致），长度为 ansLen。输出 s[ansStart .. ansStart+ansLen-1]。

为什么可以二分？
因为如果存在长度为 L 的回文，那么对于任意 k ≤ L，一定存在长度为 k 的回文（比如取那个长度为 L 的回文串的中心部分）。反之，如果不存在长度为 L 的回文，那么更长的长度也不可能存在（因为更长的回文中心部分就是长度为 L 的回文）。但注意：这个单调性是基于“存在性”而不是“最大长度”，但因为我们是从小到大二分寻找最大可行长度，所以是有效的。

步骤 3：check(mid) 函数的实现

函数目标：检查字符串 s 中是否存在长度为 len 的回文子串，如果存在返回其中一个的起始下标（0-indexed）。

从起始下标 i = 0 开始，到 i = n - len 结束，滑动窗口。
对于每个窗口 s[i..i+len-1]：
- 计算其正向哈希值 hash1 = getHash(i, i+len-1)。
- 计算其反向哈希值：这个子串的反转对应于 s' 中的子串 s'[n-(i+len-1)-1 .. n-i-1]，即 s'[n-i-len .. n-i-1]。计算该子串的哈希值 hash2 = getHashReverse(n-i-len, n-i-1)。
- 如果 hash1 == hash2（对于双哈希，需要两套哈希都相等），则说明该子串是回文（在哈希意义下，冲突概率极低），返回起始位置 i。
如果遍历完所有窗口都没找到，返回 -1。

步骤 4：双哈希降低冲突

为了更安全，我们使用两套哈希参数 (base1, mod1) 和 (base2, mod2)。计算两组前缀哈希 pre1[], pre2[] 和对应的 pow1[], pow2[]。在比较时，要求两个哈希值分别相等才认为子串相等。

复杂度分析

时间复杂度：
- 预处理哈希：O(n)。
- 二分查找：O(log n) 轮。
- 每轮 check(mid)：O(n) 次窗口滑动，每次比较 O(1) 哈希计算。
- 总时间：O(n log n)。
空间复杂度：O(n)，用于存储哈希数组。

举例说明

以 s = "babad" 为例：

预处理正反字符串哈希。
二分查找：初始 left=1, right=5。
- mid=3，检查是否存在长度为3的回文。滑动窗口："bab"（是），返回起始0。更新 ansLen=3, ansStart=0, left=4。
- mid=4，检查长度为4的回文："baba"（否），"abad"（否），返回-1。right=3。
- left=4 > right=3，结束。
最长回文长度 ansLen=3，起始 ansStart=0，输出 "bab"。

关键点总结

该方法的核心是利用哈希在 O(1) 时间内比较任意子串与其反转是否相等。
二分查找利用了回文长度存在的单调性来加速搜索。
双哈希是防止冲突的实用技巧，确保答案正确。
虽然理论最坏情况（哈希冲突）可能出错，但在实践中通过选择合适的基数和模数，可以做到几乎 100% 正确，且效率比动态规划（O(n²)）更优（尤其是对于较长字符串）。

你可以尝试实现这个算法，并对比中心扩展法（O(n²) 时间，O(1) 空间）和动态规划（O(n²) 时间，O(n²) 空间），体会哈希方法的折中优势。

哈希算法题目：最长回文子串题目描述给你一个字符串 s ，找到 s 中最长的回文子串。回文串是一个正着读和反着读都一样的字符串。例如， "babad" 的最长回文子串可以是 "bab" 或 "aba" ； "cbbd" 的最长回文子串是 "bb" 。这道题通常有多种解法，如动态规划、中心扩展算法等。我们将重点讲解一种利用哈希算法的巧妙方法，它基于字符串哈希和二分查找，可以在平均 O(n log n) 时间内解决，并且空间复杂度为 O(n)。这种方法的核心思想是，如果我们能快速判断一个子串是否是回文，那么就可以通过长度来二分搜索可能的最长回文长度。解题思路与步骤我们不会使用暴力枚举所有子串（O(n²) 个子串，每个检查 O(n)，总计 O(n³) 太慢）。而是采用以下步骤：预处理字符串哈希：计算字符串 s 的前缀哈希和后缀哈希。这允许我们在 O(1) 时间内计算任意子串的正向哈希值和反向哈希值。利用二分查找确定最长回文长度：对于一个给定的长度 L ，我们可以用 O(n) 时间检查 s 中是否存在长度为 L 的回文子串。由于回文长度满足单调性（如果存在长度为 L 的回文，那么一定存在长度 ≤ L 的回文），我们可以对可能的长度进行二分查找。检查固定长度的回文：对于给定的长度 L ，我们滑动一个长度为 L 的窗口遍历字符串。对每个窗口内的子串，用预处理好的哈希值在 O(1) 时间内判断其正向和反向哈希是否相等（需注意处理冲突，但通常双哈希可解决）。如果相等，则该子串是回文，记录其起始位置。整合结果：二分查找结束后，我们就找到了最长回文子串的长度，同时也知道了一个（或多个）起始位置，从而可以输出这个子串。详细讲解步骤 1：字符串哈希的基础我们选择一种常见的滚动哈希方法：将字符串看作一个某进制（比如基数 base = 131 或 13331 ，通常选质数）的数，然后对一个较大的质数（如 mod = 10^9 + 7 ）取模。为了避免哈希冲突，实际中常使用双哈希，即用两个不同的基数和模数计算两套哈希值，只有当两套哈希值都相等时才认为字符串相等，这能极大降低冲突概率。定义：设字符串 s 的长度为 n ，下标从 1 开始（方便计算）。 pre1[i] 表示 s[1..i] 的前缀哈希值（使用第一套哈希参数）。 pow1[i] 表示 base1^i % mod1 ，用于快速计算任意子串的哈希。递推公式： pre1[i] = (pre1[i-1] * base1 + s[i]) % mod1 pow1[i] = (pow1[i-1] * base1) % mod1 计算子串 s[ l..r] 的哈希值： hash1(l, r) = (pre1[r] - pre1[l-1] * pow1[r-l+1] % mod1 + mod1) % mod1 同理，我们计算后缀哈希 suf1[i] 表示 s[i..n] 的哈希值，但为了判断回文更方便，我们通常直接计算反向字符串的前缀哈希。设 s' 为 s 的反转字符串，计算 s' 的前缀哈希 pre1' 。这样，原串 s[l..r] 的反向串就是 s'[n-r+1..n-l+1] ，其哈希值可以用 pre1' 快速算出。步骤 2：二分查找框架最长回文子串的长度 ansLen 一定在 0 到 n 之间。我们可以二分查找这个长度。初始化 left = 1 , right = n , ansStart = 0 。当 left <= right 时：取候选长度 mid = (left + right) / 2 。调用函数 check(mid) ，检查是否存在长度为 mid 的回文子串。如果存在，返回一个起始位置 pos （或 true 并记录位置），否则返回 -1。如果 check(mid) 找到了回文（返回的位置不是 -1），则更新 ansLen = mid , ansStart = pos ，并尝试更长的长度，即 left = mid + 1 。否则，说明当前长度 mid 不存在回文，尝试更短的长度，即 right = mid - 1 。二分结束后， ansStart 是某个最长回文子串的起始位置（0-indexed 或 1-indexed 需一致），长度为 ansLen 。输出 s[ansStart .. ansStart+ansLen-1] 。为什么可以二分？因为如果存在长度为 L 的回文，那么对于任意 k ≤ L，一定存在长度为 k 的回文（比如取那个长度为 L 的回文串的中心部分）。反之，如果不存在长度为 L 的回文，那么更长的长度也不可能存在（因为更长的回文中心部分就是长度为 L 的回文）。但注意：这个单调性是基于“存在性”而不是“最大长度”，但因为我们是从小到大二分寻找最大可行长度，所以是有效的。步骤 3：check(mid) 函数的实现函数目标：检查字符串 s 中是否存在长度为 len 的回文子串，如果存在返回其中一个的起始下标（0-indexed）。从起始下标 i = 0 开始，到 i = n - len 结束，滑动窗口。对于每个窗口 s[i..i+len-1] ：计算其正向哈希值 hash1 = getHash(i, i+len-1) 。计算其反向哈希值：这个子串的反转对应于 s' 中的子串 s'[n-(i+len-1)-1 .. n-i-1] ，即 s'[n-i-len .. n-i-1] 。计算该子串的哈希值 hash2 = getHashReverse(n-i-len, n-i-1) 。如果 hash1 == hash2 （对于双哈希，需要两套哈希都相等），则说明该子串是回文（在哈希意义下，冲突概率极低），返回起始位置 i 。如果遍历完所有窗口都没找到，返回 -1。步骤 4：双哈希降低冲突为了更安全，我们使用两套哈希参数 (base1, mod1) 和 (base2, mod2) 。计算两组前缀哈希 pre1[], pre2[] 和对应的 pow1[], pow2[] 。在比较时，要求两个哈希值分别相等才认为子串相等。复杂度分析时间复杂度：预处理哈希：O(n)。二分查找：O(log n) 轮。每轮 check(mid)：O(n) 次窗口滑动，每次比较 O(1) 哈希计算。总时间：O(n log n)。空间复杂度：O(n)，用于存储哈希数组。举例说明以 s = "babad" 为例：预处理正反字符串哈希。二分查找：初始 left=1, right=5。 mid=3，检查是否存在长度为3的回文。滑动窗口："bab"（是），返回起始0。更新 ansLen=3, ansStart=0, left=4。 mid=4，检查长度为4的回文："baba"（否），"abad"（否），返回-1。right=3。 left=4 > right=3，结束。最长回文长度 ansLen=3，起始 ansStart=0，输出 "bab"。关键点总结该方法的核心是利用哈希在 O(1) 时间内比较任意子串与其反转是否相等。二分查找利用了回文长度存在的单调性来加速搜索。双哈希是防止冲突的实用技巧，确保答案正确。虽然理论最坏情况（哈希冲突）可能出错，但在实践中通过选择合适的基数和模数，可以做到几乎 100% 正确，且效率比动态规划（O(n²)）更优（尤其是对于较长字符串）。你可以尝试实现这个算法，并对比中心扩展法（O(n²) 时间，O(1) 空间）和动态规划（O(n²) 时间，O(n²) 空间），体会哈希方法的折中优势。