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

题目描述

“快乐前缀”定义为：对于一个字符串 s，如果它的某个非空前缀（长度小于字符串长度）同时也是它的后缀，那么这个前缀就叫做“快乐前缀”。

给定一个字符串 s，请返回它的最长快乐前缀。如果不存在满足要求的前缀，就返回空字符串 ""。

示例1
输入：s = "level"
输出："l"
解释：快乐前缀有 "l"（前缀"l"，后缀"l"），但最长的只有 "l"。实际上 "level" 前缀 "lev" 不是后缀，后缀是 "vel"。

示例2
输入：s = "ababab"
输出："abab"
解释："abab" 既是前缀（s[0:4]），也是后缀（s[2:6]）。

示例3
输入：s = "a"
输出：""
解释：长度小于2的字符串没有非空快乐前缀。

解题过程详解

第一步：理解问题核心

我们需要找出一个字符串 s 的最长前缀，这个前缀必须同时是 s 的后缀，但不能等于整个字符串（长度要小于 len(s)）。
这本质上是寻找字符串的最长公共前缀后缀（LPS 的变种，但不需要整个 KMP 预处理表，只需找最长一个）。

举例
s = "abcab"
检查前缀-后缀对：

• 长度 4：前缀"abca"，后缀"bcab" ❌
• 长度 3：前缀"abc"，后缀"cab" ❌
• 长度 2：前缀"ab"，后缀"ab" ✅
  所以最长快乐前缀是 "ab"。

第二步：暴力法思路（用于理解，不可用）

最简单的想法是：

1. 从可能的最大长度 len(s)-1 开始向下尝试。
2. 对每个长度 L，比较 s[0:L] 和 s[len(s)-L:len(s)] 是否相等。
3. 第一个匹配的长度就得到最长快乐前缀。

缺点：
在比较长度为 L 的子串时，每次需要 O(L) 时间，总复杂度 O(n²)，对于长字符串会超时。

第三步：引入滚动哈希（Rabin-Karp 思想）

为了快速比较前缀和后缀，我们可以在一次遍历中计算前缀哈希和后缀哈希，在常数时间内判断子串是否相等。

滚动哈希公式（常用多项式哈希）：
对于一个字符串 t，哈希可定义为：

hash(t) = (t[0]*p^{L-1} + t[1]*p^{L-2} + ... + t[L-1]*p^{0}) mod M

其中 p 是素数基数（如 31, 131），M 是大质数（如 1e9+7）。

在滚动哈希中，当我们知道长度为 L 的前缀哈希，要计算长度 L+1 的前缀哈希时：

new_hash = (old_hash * p + new_char) mod M

后缀哈希类似，但注意方向：从右向左计算时，也可以用类似方法，但更方便的是：我们直接比较前缀哈希和后缀哈希，前提是它们长度相同且起始位置不同。

第四步：具体哈希比较方案

设字符串长度 n。
定义：

• prefix_hash 表示从 0 开始的子串的哈希。
• suffix_hash 表示从某个位置开始长度为 L 的子串的哈希，要让它等于从结尾往前推 L 长度的后缀。

技巧：
我们可以一次遍历，每次增加一个字符：

1. 计算从开头到当前位置 i 的前缀的哈希 pre_hash。
2. 计算从当前位置 i 开始到末尾的后缀的哈希 suf_hash 吗？不，更方便的是：计算从位置 n-i-1 到末尾的长度为 i+1 的子串的哈希，并与前缀哈希比较。

但为了避免反向计算的麻烦，我们可以：

• 从左到右计算前缀哈希。
• 从右到左计算后缀哈希（即从末尾开始向左扩展），但每次扩展是增加左边一个字符，所以计算时：

suffix_hash = (s[j] * p^{i} + suffix_hash) mod M

其中 j 是从右向左的指针。

更简单且不易错的方法是：只用一个方向的前进计算，但比较时用长度 L 的前缀和最后 L 个字符组成后缀的哈希。

第五步：优化为单次遍历

我们可以在一次遍历中同时维护前缀哈希和后缀哈希：

• 从左到右，每次增加一个字符到前缀中，更新 prefix_hash。
• 同时，从右到左，我们也在扩展后缀，但为了同步长度，我们用一个变量 suffix_hash 记录从右端开始长度为当前遍历长度的子串的哈希，注意方向：
  后缀的扩展是：原来后缀哈希乘以 p 加上新字符（新字符是 s[n-1-i]）。
  为什么乘以 p？因为原来后缀对应的是低位，往左扩展时，新字符是更高一位。

具体：

n = len(s)
prefix_hash = 0
suffix_hash = 0
pow_val = 1
longest = ""
for i in range(n-1):  # 最长快乐前缀长度最多 n-1
    c1 = s[i]
    c2 = s[n-1-i]
    # 更新前缀哈希：从左向右
    prefix_hash = (prefix_hash * p + ord(c1)) % MOD
    # 更新后缀哈希：从右向左，注意后缀是从右往左扩展的
    suffix_hash = (ord(c2) * pow_val + suffix_hash) % MOD
    pow_val = (pow_val * p) % MOD
    # 比较哈希
    if prefix_hash == suffix_hash:
        # 还需要验证一次（极小概率哈希冲突），但一般题目不要求
        # 但安全起见可以比较字符串
        if s[:i+1] == s[n-1-i:]:
            longest = s[:i+1]

注意：这里 i 是当前扩展的长度减 1，长度为 i+1。

第六步：验证例子

以 s = "ababab" 为例，p=31, MOD=1e9+7：

初始化：pre=0, suf=0, pow_val=1, longest=""

i=0, c1='a', c2='b'（最后一个字符）
pre = (031+97) % M = 97
suf = (981 + 0) % M = 98
pow_val=31
不等，继续

i=1, c1='b', c2='a'（倒数第二个字符）
pre = (9731+98) = 3105
suf = (9731 + 98) = 3105
pow_val=961
相等，且 s[:2]="ab" 与 s[4:]="ab" 相等，longest="ab"

i=2, c1='a', c2='b'
pre = (310531+97) = 96232
suf = (98961 + 3105) = 94243
不等

i=3, c1='b', c2='a'
pre = (9623231+98) = 2983290
suf = (9729791 + 94243) = 2983290
相等，且 s[:4]="abab" 与 s[2:]="abab" 相等，longest="abab"

i=4, c1='a', c2='b'
pre 更新，suf 更新，不等
结束，返回 "abab"。

第七步：边界与复杂度

• 时间 O(n)，只需一次遍历。
• 空间 O(1)。
• 注意：如果哈希冲突，虽然概率极低，但严谨情况下可以在哈希相等时再比较一次字符串（O(L)），不影响平均 O(n) 复杂度。

最终实现（Python）

def longestHappyPrefix(s: str) -> str:
    n = len(s)
    if n <= 1:
        return ""
    p = 31
    MOD = 10**9 + 7
    prefix_hash = 0
    suffix_hash = 0
    pow_val = 1
    longest = ""
    for i in range(n - 1):
        c1 = s[i]
        c2 = s[n - 1 - i]
        prefix_hash = (prefix_hash * p + ord(c1)) % MOD
        suffix_hash = (ord(c2) * pow_val + suffix_hash) % MOD
        pow_val = (pow_val * p) % MOD
        if prefix_hash == suffix_hash:
            if s[:i + 1] == s[n - i - 1:]:
                longest = s[:i + 1]
    return longest

这个方法在 O(n) 时间内找到最长快乐前缀，利用了滚动哈希快速比较任意前缀与等长的后缀，避免了暴力 O(n²) 的比较。