哈希算法题目：最长回文子串
字数 2500 2025-10-26 09:00:52

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

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。回文串是正着读和反着读都一样的字符串。你需要实现一个函数，输入字符串 s，返回其最长回文子串。

解题过程：

  1. 问题理解与核心思路
    首先，我们需要理解什么是回文子串。例如，在字符串 "babad" 中，"bab" 和 "aba" 都是回文子串。我们的目标是找到最长的那个。
    一个直接的思路是，枚举字符串中所有可能的子串，并判断它们是否是回文串，然后记录下最长的。但这种方法的时间复杂度会非常高（O(n³)），对于较长的字符串效率极低。
    我们可以利用哈希算法结合“滚动哈希”的技巧，来实现一个名为“ Rabin-Karp 算法”的变种，以更高效地解决这个问题。其核心思想是：通过哈希值来快速判断一个子串是否可能是回文串，从而避免每次都进行完整的字符比较。

  2. 引入滚动哈希
    滚动哈希允许我们在常数时间内计算出一个滑动窗口内子串的哈希值。为了判断回文，我们需要同时计算子串的正向哈希和反向哈希。

    • 我们选择两个基数 base 和模数 mod，以减少哈希冲突。通常 base 取一个大于字符集大小的质数（如131），mod 取一个大质数（如 1e9+7）。
    • 定义两个数组：
      • prefixHash[i] 表示字符串 s 从下标0到下标i的子串的正向哈希值。
      • suffixHash[i] 表示字符串 s 从下标i到字符串末尾的子串的反向哈希值（计算方式与正向类似，但方向相反）。
    • 哈希的计算公式（以正向为例，使用多项式哈希）：
      prefixHash[i] = (prefixHash[i-1] * base + (s[i] - 'a' + 1)) % mod
    • 这样，对于子串 s[l:r]（包含l和r），其正向哈希值可以通过 prefixHash 在常数时间内计算得出：
      hash_forward = (prefixHash[r] - prefixHash[l-1] * pow(base, r-l+1, mod)) % mod
      （需要处理负数和取模，pow(base, len, mod) 是计算 base^len % mod 的预计算值）
    • 同样地，我们可以计算出该子串的反向哈希值 hash_backward。如果 hash_forward == hash_backward，则该子串很可能是回文串。

  3. 结合中心扩展法
    由于直接比较哈希值可能会存在冲突（不同的字符串有相同的哈希值），我们不能完全依赖哈希值做最终判断。因此，一个稳健的方法是结合“中心扩展法”。

    • 中心扩展法的思想是：每一个回文串都有一个“中心”。我们可以遍历字符串，把每个位置（以及两个位置中间）当作中心，然后向两边扩展，直到字符不相等为止，从而得到以该中心展开的最长回文子串。
    • 但是，纯中心扩展法在最坏情况下时间复杂度是 O(n²)。
    • 优化策略：我们可以使用滚动哈希来快速判断一个子串是否“可能”是回文。具体步骤如下：
      1. 首先，我们预计算字符串的正向哈希数组 prefixHash 和反向哈希数组 suffixHash，以及基数 base 的各次幂的模 mod 值，存入数组 pow_base。
      2. 我们遍历所有可能的回文中心（共有 2n-1 个，包括字符位置和字符间位置）。
      3. 对于每个中心，我们不是盲目地一步步扩展，而是可以先利用二分查找确定一个可能的最大回文半径。
        • 假设当前中心是 c，我们已知当前可能的最大半径不会超过 min(c, n-1-c)（考虑边界）。
        • 我们在可能的半径范围 [0, max_possible_radius] 内进行二分查找。对于中点半径 mid，我们计算以 c 为中心、半径为 mid 的子串的正向哈希和反向哈希。
        • 如果两个哈希值相等，说明半径为 mid 的子串很可能是一个回文串，那么我们可以尝试更大的半径（二分查找的右半部分）。否则，我们尝试更小的半径（左半部分）。
      4. 通过二分查找，我们找到一个最大的半径 max_r，使得以 c 为中心、半径为 max_r 的子串的哈希值相等。
      5. 重要：由于哈希冲突的存在，我们找到的这个子串只是“极大概率”是回文串。为了确保正确性，我们需要对这个特定子串 s[c-max_r : c+max_r] 进行一次真正的回文校验（即直接比较字符）。因为我们已经将候选范围缩小到了一个特定的子串，所以这次校验的代价是 O(n) 但只发生常数次，均摊下来不影响整体复杂度。
      6. 如果校验通过，这个子串就是以当前中心展开的最长回文子串。我们记录其长度和起始位置。
      7. 如果校验不通过（发生了哈希冲突），我们将半径 max_r 减一，再次进行哈希比较和回文校验，直到找到真正的最大回文半径。

  4. 算法流程总结

    1. 预处理：计算 prefixHash, suffixHash, pow_base 数组。
    2. 遍历中心：对于每个可能的回文中心。
    3. 二分查找半径：在当前中心的最大可能半径范围内，使用二分查找结合哈希比较，快速找到一个最大的候选半径 max_r。
    4. 回文校验：对候选子串进行最终的回文校验，确保结果正确。
    5. 更新结果：如果当前找到的回文子串比之前记录的最长子串更长，则更新最长子串的起始位置和长度。
    6. 返回结果：根据记录的最长子串起始位置和长度，返回该子串。

  5. 复杂度分析

    • 时间复杂度：预处理哈希和幂次数组需要 O(n)。遍历中心点有 O(n) 个。对每个中心点，二分查找半径需要 O(log n) 次哈希比较（每次比较是 O(1)）。最终的精确校验虽然最坏是 O(n)，但由于哈希冲突极少发生，且即使发生也只需校验少数几次，均摊后可以视为常数。因此，总时间复杂度为 O(n log n)。
    • 空间复杂度：O(n)，用于存储哈希数组和幂次数组。

这种方法通过哈希进行快速筛选，再辅以精确校验，在效率和正确性之间取得了很好的平衡，是解决最长回文子串问题的一个高效算法。

哈希算法题目：最长回文子串 题目描述：给定一个字符串 s，找到 s 中最长的回文子串。回文串是正着读和反着读都一样的字符串。你需要实现一个函数，输入字符串 s，返回其最长回文子串。 解题过程： 问题理解与核心思路 首先，我们需要理解什么是回文子串。例如，在字符串 "babad" 中，"bab" 和 "aba" 都是回文子串。我们的目标是找到最长的那个。 一个直接的思路是，枚举字符串中所有可能的子串，并判断它们是否是回文串，然后记录下最长的。但这种方法的时间复杂度会非常高（O(n³)），对于较长的字符串效率极低。 我们可以利用哈希算法结合“滚动哈希”的技巧，来实现一个名为“ Rabin-Karp 算法”的变种，以更高效地解决这个问题。其核心思想是：通过哈希值来快速判断一个子串是否可能是回文串，从而避免每次都进行完整的字符比较。 引入滚动哈希 滚动哈希允许我们在常数时间内计算出一个滑动窗口内子串的哈希值。为了判断回文，我们需要同时计算子串的正向哈希和反向哈希。 我们选择两个基数 base 和模数 mod ，以减少哈希冲突。通常 base 取一个大于字符集大小的质数（如131）， mod 取一个大质数（如 1e9+7）。 定义两个数组： prefixHash[i] 表示字符串 s 从下标0到下标i的子串的正向哈希值。 suffixHash[i] 表示字符串 s 从下标i到字符串末尾的子串的反向哈希值（计算方式与正向类似，但方向相反）。 哈希的计算公式（以正向为例，使用多项式哈希）： prefixHash[i] = (prefixHash[i-1] * base + (s[i] - 'a' + 1)) % mod 这样，对于子串 s[ l:r]（包含l和r），其正向哈希值可以通过 prefixHash 在常数时间内计算得出： hash_forward = (prefixHash[r] - prefixHash[l-1] * pow(base, r-l+1, mod)) % mod （需要处理负数和取模， pow(base, len, mod) 是计算 base^len % mod 的预计算值） 同样地，我们可以计算出该子串的反向哈希值 hash_backward 。如果 hash_forward == hash_backward ，则该子串 很可能 是回文串。 结合中心扩展法 由于直接比较哈希值可能会存在冲突（不同的字符串有相同的哈希值），我们不能完全依赖哈希值做最终判断。因此，一个稳健的方法是结合“中心扩展法”。 中心扩展法的思想是：每一个回文串都有一个“中心”。我们可以遍历字符串，把每个位置（以及两个位置中间）当作中心，然后向两边扩展，直到字符不相等为止，从而得到以该中心展开的最长回文子串。 但是，纯中心扩展法在最坏情况下时间复杂度是 O(n²)。 优化策略 ：我们可以 使用滚动哈希来快速判断一个子串是否“可能”是回文 。具体步骤如下： 首先，我们预计算字符串的正向哈希数组 prefixHash 和反向哈希数组 suffixHash ，以及基数 base 的各次幂的模 mod 值，存入数组 pow_base 。 我们遍历所有可能的回文中心（共有 2n-1 个，包括字符位置和字符间位置）。 对于每个中心，我们不是盲目地一步步扩展，而是可以先利用 二分查找 确定一个可能的最大回文半径。 假设当前中心是 c ，我们已知当前可能的最大半径不会超过 min(c, n-1-c) （考虑边界）。 我们在可能的半径范围 [0, max_possible_radius] 内进行二分查找。对于中点半径 mid ，我们计算以 c 为中心、半径为 mid 的子串的正向哈希和反向哈希。 如果两个哈希值相等，说明半径为 mid 的子串很可能是一个回文串，那么我们可以尝试更大的半径（二分查找的右半部分）。否则，我们尝试更小的半径（左半部分）。 通过二分查找，我们找到一个最大的半径 max_r ，使得以 c 为中心、半径为 max_r 的子串的哈希值相等。 重要 ：由于哈希冲突的存在，我们找到的这个子串只是“极大概率”是回文串。为了确保正确性，我们需要对这个特定子串 s[c-max_r : c+max_r] 进行一次 真正的回文校验 （即直接比较字符）。因为我们已经将候选范围缩小到了一个特定的子串，所以这次校验的代价是 O(n) 但只发生常数次，均摊下来不影响整体复杂度。 如果校验通过，这个子串就是以当前中心展开的最长回文子串。我们记录其长度和起始位置。 如果校验不通过（发生了哈希冲突），我们将半径 max_r 减一，再次进行哈希比较和回文校验，直到找到真正的最大回文半径。 算法流程总结 预处理 ：计算 prefixHash , suffixHash , pow_base 数组。 遍历中心 ：对于每个可能的回文中心。 二分查找半径 ：在当前中心的最大可能半径范围内，使用二分查找结合哈希比较，快速找到一个最大的候选半径 max_r 。 回文校验 ：对候选子串进行最终的回文校验，确保结果正确。 更新结果 ：如果当前找到的回文子串比之前记录的最长子串更长，则更新最长子串的起始位置和长度。 返回结果 ：根据记录的最长子串起始位置和长度，返回该子串。 复杂度分析 时间复杂度 ：预处理哈希和幂次数组需要 O(n)。遍历中心点有 O(n) 个。对每个中心点，二分查找半径需要 O(log n) 次哈希比较（每次比较是 O(1)）。最终的精确校验虽然最坏是 O(n)，但由于哈希冲突极少发生，且即使发生也只需校验少数几次，均摊后可以视为常数。因此，总时间复杂度为 O(n log n)。 空间复杂度 ：O(n)，用于存储哈希数组和幂次数组。 这种方法通过哈希进行快速筛选，再辅以精确校验，在效率和正确性之间取得了很好的平衡，是解决最长回文子串问题的一个高效算法。