题目描述

快乐前缀 是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。

给你一个字符串 s，请你返回它的 最长快乐前缀。

如果不存在满足题意的前缀，则返回一个空字符串。

样例

输入：s = "level"
输出："l"
解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）
和 4 个后缀（"l", "el", "vel", "evel"）。
最长的既是前缀也是后缀的字符串是 "l"。

输入：s = "ababab"
输出："abab"
解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。

输入：s = "leetcodeleet"
输出："leet"

输入：s = "a"
输出：""

限制

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

算法

(KMP算法) $O(n)$

1. 通过 KMP 算法可以得到 next 数组，题目求的就是最后一个位置的 next 的值。
2. 具体 KMP 算法的流程可以在分享中搜索 KMP。

时间复杂度

• KMP 算法构造 next 数组的时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储 next 数组和答案。

C++ 代码

class Solution {
public:
    string longestPrefix(string s) {
        int n = s.length();
        vector<int> p(n);

        p[0] = -1;
        int j = -1;
        for (int i = 1; i < n; i++) {
            while (j != -1 && s[j + 1] != s[i])
                j = p[j];

            if (s[j + 1] == s[i])
                j++;

            p[i] = j;
        }

        return s.substr(0, p[n - 1] + 1);
    }
};