最长快乐前缀
字数 2093 2025-12-06 19:10:19

最长快乐前缀

题目描述：
给定一个字符串 s，请找出 s 的 最长快乐前缀。
快乐前缀定义：一个既是 s 的 非空前缀 又是 s 的 非空后缀 的子字符串。
如果不存在满足条件的快乐前缀，则返回空字符串 ""。

示例 1：
输入：s = "level"
输出："l"
解释：s 的所有快乐前缀包括 "l" 和 "level"，最长的是 "l"。

示例 2：
输入：s = "ababab"
输出："abab"
解释："abab" 是前缀 "ababab" 和后缀 "ababab" 的共同部分。

示例 3：
输入：s = "a"
输出：""
解释：没有既是非空前缀又是非空后缀的子串（因为不能是字符串本身）。

解题思路

题目本质是寻找字符串的 最长相同前后缀（LPS 概念，但不包括整个字符串本身）。
一种高效的解法是使用 滚动哈希（Rabin-Karp 思想），在 O(n) 时间内完成。

滚动哈希核心思想：
将字符串视为一个多进制数，通过哈希值快速比较前缀和后缀是否相等。

  • 从左到右计算前缀哈希值（正向哈希）
  • 从右到左计算后缀哈希值（反向哈希，但注意方向匹配）
  • 当某个长度的前缀哈希值等于相同长度的后缀哈希值时，说明找到了一个快乐前缀

详细步骤

步骤 1：理解“相同前后缀”的含义

对于字符串 s，长度为 n。
设长度 k 的子串 s[0:k] 是前缀，s[n-k:n] 是后缀。
当这两个子串相等时，就是一个长度为 k 的快乐前缀。
我们要找最大的 k（1 ≤ k < n）。

步骤 2：选择哈希函数

为了避免哈希冲突，可以使用双哈希（两个不同模数）。
常用模数：

  • MOD1 = 10^9 + 7
  • MOD2 = 10^9 + 9
    进制基数 base 通常取一个质数，如 31、131 等。

定义：
hash1 = (hash1 * base + char_val) % MOD1
类似计算 hash2。

但这里我们不仅要算前缀哈希，还要快速得到后缀哈希。
技巧：
后缀 s[n-k:n] 的哈希可以通过正向哈希公式从 n-k 开始计算，但更简单的方法是：
在从左到右计算前缀哈希的同时，也计算“反向前缀哈希”（即把字符串反转后计算哈希）。但要注意后缀对应原始字符串的某段，我们可以用另一种方式：
用两个变量分别记录前缀哈希和后缀哈希的累积值，但后缀哈希是从右向左累积的。

具体做法：

  • 从左到右遍历每个字符，计算前缀的哈希值（正常顺序）
  • 同时，从右到左（从字符串开头开始模拟后缀累积）比较麻烦，我们可以这样等价：
    比较 s[0:k] 和 s[n-k:n] 是否相等，相当于比较它们两个子串的哈希值。
    我们可以用前缀哈希数组直接得到 s[0:k] 的哈希值，而 s[n-k:n] 的哈希值可以通过后缀哈希公式用前缀哈希的差值得到（即把整个字符串的前缀哈希数组算好，然后任意子串哈希 = (hash[r] - hash[l-1]*base^(r-l+1)) mod MOD）。

步骤 3：算法步骤

  1. 预处理前缀哈希数组 hash[i] 表示 s[0:i] 的哈希值（i 从 0 到 n）。
  2. 预处理 pow[i] 表示 base^i mod MOD。
  3. 对每个长度 len 从 n-1 递减到 1（找最大）：
    • 前缀子串 s[0:len] 的哈希值 h1 = hash[len]
    • 后缀子串 s[n-len:n] 的哈希值 h2 = (hash[n] - hash[n-len] * pow[len]) mod MOD
    • 如果 h1 等于 h2，再比较字符串是否真的相等（防止哈希冲突），如果相等则返回 s[0:len]。
  4. 如果循环结束没找到，返回空字符串。

注意：由于我们要找最长，所以从大到小枚举长度。

举例说明

s = "ababab"

base = 131, MOD = 10^9+7

n=6

前缀哈希（假设用整数表示，这里简化）：

  • hash[0]=0
  • hash[1]='a'
  • hash[2]="ab"
  • ...
  • hash[6]="ababab"

计算长度 len=4：

  • 前缀 s[0:4]="abab" 哈希值 h1 = hash[4]
  • 后缀 s[2:6]="abab" 索引 n-len=2, 到 6
  • 用公式 h2 = (hash[6] - hash[2]*pow[4]) mod MOD
  • 如果 h1==h2，再比较字符串，相等，则找到快乐前缀 "abab"。

因为 len=5 时前缀 "ababa" 不等于后缀 "babab"，所以最长是 4。

时间复杂度

  • 计算前缀哈希 O(n)
  • 枚举长度 O(n)（但可以在比较时用 O(1) 时间比较哈希值）
  • 总 O(n)

空间复杂度

O(n) 存储哈希数组。

最终实现要点

  • 用双模数哈希降低冲突概率
  • 从长到短枚举快乐前缀长度
  • 验证时先比哈希值，再比字符串（可避免冲突）

这样就找到了最长的既是前缀又是后缀的子串。

最长快乐前缀 题目描述： 给定一个字符串 s，请找出 s 的 最长快乐前缀 。 快乐前缀定义：一个既是 s 的 非空前缀 又是 s 的 非空后缀 的子字符串。 如果不存在满足条件的快乐前缀，则返回空字符串 ""。 示例 1： 输入：s = "level" 输出："l" 解释：s 的所有快乐前缀包括 "l" 和 "level"，最长的是 "l"。 示例 2： 输入：s = "ababab" 输出："abab" 解释："abab" 是前缀 "ababab" 和后缀 "ababab" 的共同部分。 示例 3： 输入：s = "a" 输出："" 解释：没有既是非空前缀又是非空后缀的子串（因为不能是字符串本身）。 解题思路 题目本质是寻找字符串的 最长相同前后缀 （LPS 概念，但不包括整个字符串本身）。 一种高效的解法是使用 滚动哈希 （Rabin-Karp 思想），在 O(n) 时间内完成。 滚动哈希核心思想 ： 将字符串视为一个多进制数，通过哈希值快速比较前缀和后缀是否相等。 从左到右计算前缀哈希值（正向哈希） 从右到左计算后缀哈希值（反向哈希，但注意方向匹配） 当某个长度的前缀哈希值等于相同长度的后缀哈希值时，说明找到了一个快乐前缀 详细步骤 步骤 1：理解“相同前后缀”的含义 对于字符串 s，长度为 n。 设长度 k 的子串 s[ 0:k] 是前缀，s[ n-k:n ] 是后缀。 当这两个子串相等时，就是一个长度为 k 的快乐前缀。 我们要找最大的 k（1 ≤ k < n）。 步骤 2：选择哈希函数 为了避免哈希冲突，可以使用 双哈希 （两个不同模数）。 常用模数： MOD1 = 10^9 + 7 MOD2 = 10^9 + 9 进制基数 base 通常取一个质数，如 31、131 等。 定义： hash1 = (hash1 * base + char_ val) % MOD1 类似计算 hash2。 但这里我们不仅要算前缀哈希，还要快速得到后缀哈希。 技巧 ： 后缀 s[ n-k:n ] 的哈希可以通过正向哈希公式从 n-k 开始计算，但更简单的方法是： 在从左到右计算前缀哈希的同时，也计算“反向前缀哈希”（即把字符串反转后计算哈希）。但要注意后缀对应原始字符串的某段，我们可以用另一种方式： 用两个变量分别记录前缀哈希和后缀哈希的累积值，但后缀哈希是从右向左累积的。 具体做法： 从左到右遍历每个字符，计算前缀的哈希值（正常顺序） 同时，从右到左（从字符串开头开始模拟后缀累积）比较麻烦，我们可以这样等价： 比较 s[ 0:k] 和 s[ n-k:n ] 是否相等，相当于比较它们两个子串的哈希值。 我们可以用前缀哈希数组直接得到 s[ 0:k] 的哈希值，而 s[ n-k:n] 的哈希值可以通过后缀哈希公式用前缀哈希的差值得到（即把整个字符串的前缀哈希数组算好，然后任意子串哈希 = (hash[ r] - hash[ l-1]* base^(r-l+1)) mod MOD）。 步骤 3：算法步骤 预处理前缀哈希数组 hash[ i] 表示 s[ 0:i ] 的哈希值（i 从 0 到 n）。 预处理 pow[ i ] 表示 base^i mod MOD。 对每个长度 len 从 n-1 递减到 1（找最大）： 前缀子串 s[ 0:len] 的哈希值 h1 = hash[ len ] 后缀子串 s[ n-len:n] 的哈希值 h2 = (hash[ n] - hash[ n-len] * pow[ len ]) mod MOD 如果 h1 等于 h2，再比较字符串是否真的相等（防止哈希冲突），如果相等则返回 s[ 0:len ]。 如果循环结束没找到，返回空字符串。 注意 ：由于我们要找最长，所以从大到小枚举长度。 举例说明 s = "ababab" base = 131, MOD = 10^9+7 n=6 前缀哈希（假设用整数表示，这里简化）： hash[ 0 ]=0 hash[ 1 ]='a' hash[ 2 ]="ab" ... hash[ 6 ]="ababab" 计算长度 len=4： 前缀 s[ 0:4]="abab" 哈希值 h1 = hash[ 4 ] 后缀 s[ 2:6 ]="abab" 索引 n-len=2, 到 6 用公式 h2 = (hash[ 6] - hash[ 2]* pow[ 4 ]) mod MOD 如果 h1==h2，再比较字符串，相等，则找到快乐前缀 "abab"。 因为 len=5 时前缀 "ababa" 不等于后缀 "babab"，所以最长是 4。 时间复杂度 计算前缀哈希 O(n) 枚举长度 O(n)（但可以在比较时用 O(1) 时间比较哈希值） 总 O(n) 空间复杂度 O(n) 存储哈希数组。 最终实现要点 用双模数哈希降低冲突概率 从长到短枚举快乐前缀长度 验证时先比哈希值，再比字符串（可避免冲突） 这样就找到了最长的既是前缀又是后缀的子串。