Hard

题目描述

如果字符串的一个非空前缀同时也是后缀（不包括字符串本身），则称这个字符串为"快乐前缀"。

给你一个字符串 s，请你返回 s 的最长快乐前缀。如果不存在符合题意的前缀，则返回一个空字符串 ""。

示例 1：

输入：s = "level"
输出："l"
解释：s 包含 4 个前缀，除了它本身外：("l", "le", "lev", "leve")，同时包含 4 个后缀：("l", "el", "vel", "evel")。最大的既是前缀又是后缀的字符串是 "l"。

示例 2：

输入：s = "ababab"
输出："abab"
解释："abab" 是最大的既是前缀又是后缀的字符串。它们可以在原字符串中重叠。

提示：

  • 1 <= s.length <= 10^5
  • s 只包含小写英文字母

解题思路

这道题要求找到字符串的最长快乐前缀，即既是前缀又是后缀的最长子串（不包括字符串本身）。

方法一：KMP 算法的 LPS 数组（推荐）

KMP 算法中的 LPS（Longest Prefix Suffix）数组正好解决了这个问题。LPS[i] 表示字符串 s[0:i+1] 的最长相同前后缀的长度。

算法步骤：

  1. 构建 LPS 数组，其中 LPS[i] 表示 s[0:i+1] 的最长相同前后缀长度
  2. 使用双指针技术：i 指向当前位置，j 指向前缀末尾
  3. 如果 s[i] == s[j]，则 LPS[i] = j + 1
  4. 否则，将 j 回退到 LPS[j-1]，直到找到匹配或 j 为 0
  5. 最终答案就是 s[0:LPS[n-1]]

方法二：滚动哈希

使用多项式哈希计算前缀和后缀的哈希值，比较是否相等。为避免哈希冲突，可以使用双哈希。

方法三：暴力枚举

枚举所有可能的前缀长度，检查对应的前缀和后缀是否相同。时间复杂度 O(n²)。

KMP 方法时间复杂度最优且最稳定，是首选解法。

代码实现

class Solution {
public:
    string longestPrefix(string s) {
        int n = s.length();
        if (n <= 1) return "";
        
        vector<int> lps(n, 0);
        int j = 0;
        
        for (int i = 1; i < n; i++) {
            while (j > 0 && s[i] != s[j]) {
                j = lps[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            lps[i] = j;
        }
        
        int len = lps[n - 1];
        return len > 0 ? s.substr(0, len) : "";
    }
};

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return ""
        
        lps = [0] * n
        j = 0
        
        for i in range(1, n):
            while j > 0 and s[i] != s[j]:
                j = lps[j - 1]
            if s[i] == s[j]:
                j += 1
            lps[i] = j
        
        length = lps[n - 1]
        return s[:length] if length > 0 else ""

public class Solution {
    public string LongestPrefix(string s) {
        int n = s.Length;
        if (n <= 1) return "";
        
        int[] lps = new int[n];
        int j = 0;
        
        for (int i = 1; i < n; i++) {
            while (j > 0 && s[i] != s[j]) {
                j = lps[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            lps[i] = j;
        }
        
        int length = lps[n - 1];
        return length > 0 ? s.Substring(0, length) : "";
    }
}

var longestPrefix = function(s) {
    const n = s.length;
    if (n <= 1) return "";
    
    const lps = new Array(n).fill(0);
    let j = 0;
    
    for (let i = 1; i < n; i++) {
        while (j > 0 && s[i] !== s[j]) {
            j = lps[j - 1];
        }
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
KMP LPS 数组O(n)O(n)
滚动哈希O(n)O(1)
暴力枚举O(n²)O(1)

相关题目