哈希算法题目：最长快乐前缀

题目描述

“最长快乐前缀”是一个经典的字符串哈希问题，其定义如下：

给你一个字符串 s，请你找出它的最长快乐前缀（happy prefix）。
“快乐前缀”定义为：既是字符串的非空前缀，也是字符串的非空后缀（即字符串的前缀和后缀完全相同），并且不能是字符串本身。

换句话说，我们需要找到字符串 s 的最长前缀，这个前缀也恰好是 s 的后缀，且长度小于 s 的长度。

示例：
输入：s = "ababab"
输出："abab"
解释：前缀 "abab" 也同时是后缀（字符串后四位是 "abab"），且长度小于 6。

输入：s = "a"
输出：""
解释：没有长度小于 1 的非空前缀/后缀。

解题思路

暴力解法是逐一比较每个可能的前缀与对应长度的后缀是否相等，但这样最坏时间复杂度是 O(n²)（n 为字符串长度），效率较低。
我们可以利用滚动哈希（Rabin-Karp 算法的思想）在 O(n) 时间内完成。

核心思想：

• 从左到右计算前缀的哈希值，从右到左计算后缀的哈希值。
• 如果某个长度的前缀哈希值等于后缀哈希值，说明它们可能相同（需注意哈希冲突，但合理选择哈希函数可避免）。
• 从长到短检查，找到的第一个符合条件的即为最长快乐前缀。

逐步讲解

步骤 1：理解“前缀哈希”与“后缀哈希”

设字符串 s 长度为 n，下标从 0 开始。
长度为 len 的前缀：s[0:len]
长度为 len 的后缀：s[n-len:n]

我们需要判断 s[0:len] 是否等于 s[n-len:n]。

步骤 2：选择哈希函数

常用滚动哈希采用多项式哈希（polynomial rolling hash）：
将字符串看作一个多进制数（基数 base），对一个大质数 mod 取模。

定义：

• 哈希值：hash(s[0:k]) = (s[0] * base^(k-1) + s[1] * base^(k-2) + ... + s[k-1]) % mod
• 为了快速计算不同子串的哈希，可以预先计算哈希前缀数组和基数的幂。

这里我们采用双哈希来降低冲突概率：

• 选择两组 (base, mod)，分别计算哈希，只有两组哈希都相等才认为字符串相同。

步骤 3：计算前缀哈希与后缀哈希

我们并不需要预先计算所有子串哈希，而是：

• 从左到右扫描，维护当前前缀哈希。
• 从右到左扫描，维护当前后缀哈希。
• 比较在相同长度时，前缀哈希是否等于后缀哈希。

但更简单的方法是：

• 预先计算整个字符串的哈希前缀数组，然后直接取出长度为 len 的前缀哈希。
• 后缀哈希可以通过计算子串 s[n-len:n] 的哈希得到，用前缀哈希数组的公式：
  hash(s[l:r]) = (hash_prefix[r] - hash_prefix[l] * pow_base[r-l]) % mod（注意调整成正数）。

步骤 4：算法步骤

1. 获取字符串长度 n，如果 n <= 1，直接返回空字符串。
2. 选择两个较大的质数作为模数，如 mod1 = 10^9+7，mod2 = 10^9+9，基数 base = 131（经验值，通常选质数）。
3. 计算两个哈希前缀数组 h1, h2，以及对应的幂数组 p1, p2。
4. 从长度 len = n-1 递减到 1 检查：
   • 前缀 s[0:len] 的哈希对 (h1_l, h2_l) 可以直接从前缀数组得到。
   • 后缀 s[n-len:n] 的哈希对 (h1_r, h2_r) 可以用前缀数组计算：
     h1_r = (h1[n] - h1[n-len] * p1[len]) % mod1（类似计算 h2_r）。
   • 如果 (h1_l, h2_l) == (h1_r, h2_r)，则找到最长快乐前缀 s[0:len]，返回。
5. 如果没找到，返回空字符串。

步骤 5：举例说明

以 s = "ababab" 为例，n = 6。

我们模拟双哈希过程（为简化，这里只展示一组哈希，实际用两组）：

• 前缀哈希数组（基数 131，mod 10^9+7）：
  h[0]=0
  h[1] = 'a' = 97
  h[2] = 97*131 + 98 = 12865
  ...（略）
• 检查 len=5：
  前缀哈希 h[5] = hash("ababa")
  后缀哈希 = hash(s[1:6]) = hash("babab")，不等。
• 检查 len=4：
  前缀哈希 h[4] = hash("abab")
  后缀哈希 = hash(s[2:6]) = hash("abab")，相等 → 找到，返回 "abab"。

步骤 6：边界情况

• 字符串长度 1：无快乐前缀。
• 全相同字符，如 "aaaa" → 最长快乐前缀是 "aaa"。
• 无快乐前缀，如 "abcd" → 返回 ""。

步骤 7：时间复杂度

• 计算前缀哈希数组：O(n)
• 检查每个长度：O(1) 每次，最多检查 n-1 次，所以 O(n)
• 总时间复杂度 O(n)，空间 O(n)（存储哈希数组和幂数组）。

代码实现（Python 示例）

def longestPrefix(s: str) -> str:
    n = len(s)
    if n <= 1:
        return ""
    
    base = 131
    mod1 = 10**9 + 7
    mod2 = 10**9 + 9
    
    h1 = [0] * (n + 1)
    h2 = [0] * (n + 1)
    p1 = [1] * (n + 1)
    p2 = [1] * (n + 1)
    
    for i in range(1, n + 1):
        h1[i] = (h1[i-1] * base + ord(s[i-1])) % mod1
        h2[i] = (h2[i-1] * base + ord(s[i-1])) % mod2
        p1[i] = (p1[i-1] * base) % mod1
        p2[i] = (p2[i-1] * base) % mod2
    
    for length in range(n-1, 0, -1):
        # 前缀 s[0:length] 的哈希
        prefix_h1 = h1[length]
        prefix_h2 = h2[length]
        # 后缀 s[n-length:n] 的哈希
        suffix_h1 = (h1[n] - h1[n-length] * p1[length]) % mod1
        suffix_h2 = (h2[n] - h2[n-length] * p2[length]) % mod2
        
        if (prefix_h1, prefix_h2) == (suffix_h1, suffix_h2):
            return s[:length]
    
    return ""

总结

这道题是滚动哈希的典型应用：

1. 理解“快乐前缀”即前后缀相同。
2. 用双哈希避免冲突，在 O(n) 时间内找到最长长度。
3. 通过前缀哈希数组快速获取任意子串哈希值进行比较。

此方法也常用于 KMP 算法中的部分匹配表（next 数组）的哈希版本，但哈希法更易理解实现。