最长快乐前缀

题目描述
给定一个字符串 s，请你找出 s 中最长的、既是其前缀（从开头开始），也是其后缀（到结尾为止）的子串，并且这个子串不能是原字符串本身。如果不存在这样的子串，则返回空字符串 ""。

例如：

• 输入: s = "level"， 输出: "l"（"l" 既是前缀 "l" 也是后缀 "l"，且 "level" 本身除外）
• 输入: s = "ababab"，输出: "abab"（"abab" 是前缀 "abab" 也是后缀 "abab"）
• 输入: s = "a"，输出: ""（因为字符串本身除外，没有其他子串）

解题过程

步骤1：理解“最长快乐前缀”的定义
我们需要找一个子串 t，满足：

1. t 是 s 的前缀，即 s 以 t 开头。
2. t 是 s 的后缀，即 s 以 t 结尾。
3. t 不能等于整个 s 本身。

换句话说，我们要找到最长的、相等的前缀和后缀（但不包括整个字符串）。这个问题在字符串算法中常被称为寻找字符串的最长相同真前缀与真后缀。

步骤2：暴力枚举的直观想法
最直接的方法是枚举所有可能的长度 len（从 1 到 n-1，n 是字符串长度），检查前 len 个字符组成的子串是否等于后 len 个字符组成的子串。取最大的 len 即可。

例如 s = "ababab"：

• len=5: 前缀 "ababa"，后缀 "babab"，不相等
• len=4: 前缀 "abab"，后缀 "abab"，相等，记录长度 4
• 继续检查更小的 len，但我们要最长，所以找到 4 就停止。

这种方法的时间复杂度是 O(n²)，因为每次比较子串需要 O(n) 时间，共有 n 次检查。对于长字符串（例如长度 10⁵），会超时。

步骤3：引入滚动哈希优化
为了避免每次比较子串时的 O(n) 字符比对，我们可以用哈希算法来加速比较。
思路是：

1. 计算字符串的哈希值时，同时维护前缀哈希和后缀哈希。
2. 比较前缀哈希值和后缀哈希值是否相等，如果相等，再验证一次字符串内容（防止哈希冲突），从而快速判断前后缀是否相同。

具体步骤

3.1 滚动哈希原理
滚动哈希把一个字符串看作一个进制数（比如基数为 131 或 13331），用一个大质数（如 2^64，利用自然溢出）取模，这样可以在 O(1) 时间内计算任意子串的哈希值。

定义：

• 设字符串长度为 n，字符用 ASCII 值。
• 用 pref[i] 表示 s[0..i] 的哈希值（前 i+1 个字符）。
• 递推公式（常用多项式哈希）：

  pref[0] = s[0] 的编码（如 ord(s[0])）
  pref[i] = (pref[i-1] * base + ord(s[i])) % mod
  

• 为了快速得到任意子串 s[l..r] 的哈希值，我们可以提前计算 pow_base[i] = base^i % mod，然后用：

  hash(l, r) = pref[r] - pref[l-1] * pow_base[r-l+1]   (取模运算)
  

3.2 本题的特殊性
在本题中，我们要比较的是长度为 len 的前缀和长度为 len 的后缀：

• 前缀：s[0..len-1]，哈希值就是 pref[len-1]
• 后缀：s[n-len..n-1]，它的哈希值可以用递推的后缀哈希，也可以用前缀哈希公式计算：
  把整个字符串当成一个数，后缀相当于从第 n-len 位到末尾的子串，可以用 hash(n-len, n-1) 公式计算，但需要提前计算前缀数组。

3.3 算法流程

1. 计算字符串 s 的所有前缀哈希值，存在数组 pref_hash 中。
2. 计算所有后缀哈希值（可以同样用前缀哈希公式，但字符串从末尾倒着算更方便，或者直接用前缀哈希推导后缀子串的哈希值）。
3. 从大到小枚举长度 len（从 n-1 到 1）：
   • 前缀 s[0:len] 的哈希值 = pref_hash[len-1]
   • 后缀 s[n-len:] 的哈希值 = 计算 hash(n-len, n-1)：

     suffix_hash = (pref_hash[n-1] - pref_hash[n-len-1] * pow_base[len]) % mod
     

   • 如果 pref_hash[len-1] == suffix_hash，再比较一次字符串内容（避免哈希冲突），如果相等，就找到了最长的快乐前缀，返回 s[:len]。
4. 如果没找到，返回空字符串。

这里注意，我们从大到小枚举长度，这样第一个找到的满足条件的，就是最长的。

步骤4：一个更简单的等价算法（KMP 的 next 数组思想）
实际上，这个问题在 KMP 算法中就是求 next[n-1] 对应的前缀长度。KMP 的 next 数组定义就是“最长相同真前缀与真后缀的长度”。
我们可以用 KMP 预处理 next 数组，然后直接得到答案长度 len = next[n-1]，返回 s[:len] 即可。
这个方法时间复杂度 O(n)，空间复杂度 O(n)，且不需要处理哈希冲突。

KMP 解法步骤：

1. 计算字符串 s 的 next 数组（长度 n）：
   • next[0] = 0
   • 对于 i 从 1 到 n-1：
     • 比较 s[i] 与 s[next[i-1]]，不断回退 next 指针直到相等或为 0
     • 更新 next[i]
2. 最后 len = next[n-1] 就是最长相同真前缀与真后缀的长度。
3. 如果 len == 0，返回空串，否则返回 s[:len]。

例子：s = "ababab"
next 数组计算过程（略）得到 next[5] = 4，所以最长快乐前缀是 s[:4] = "abab"。

步骤5：选择实现方法
在竞赛或面试中，通常两种方法都可以：

• 滚动哈希 需要处理取模和冲突检测，但思路直接。
• KMP next 数组 是标准解法，代码简洁，不易出错。

这里我们用 KMP 思想 给出最终代码（伪代码）：

function longestHappyPrefix(s):
    n = length(s)
    next = array of size n, filled with 0
    j = 0
    for i from 1 to n-1:
        while j > 0 and s[i] != s[j]:
            j = next[j-1]
        if s[i] == s[j]:
            j += 1
        next[i] = j
    len = next[n-1]
    if len == 0:
        return ""
    else:
        return s[0:len]

复杂度分析

• 时间复杂度：O(n)，一次遍历字符串。
• 空间复杂度：O(n)，存储 next 数组。

步骤6：举例验证
输入 s = "level"

• 计算 next 数组：[0,0,0,0,1]，next[4]=1
• 返回 s[:1] = "l" ✅

输入 s = "a"

• next 数组：[0]，len=0，返回空串 ✅

这样，我们就通过 KMP 的 next 数组思想，高效解决了“最长快乐前缀”问题，避免了 O(n²) 的暴力枚举。这个方法本质上是哈希思想的另一种高效实现，利用了字符串自匹配的特性。