题目描述

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

给你一个字符串 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 只含有小写英文字母

算法分析

字符串哈希

• 对于每段字符串用一个数字唯一标识，依次枚举每个前缀字符串和后缀字符串，若相等则更新长度

详细版看 y 总的Acwing841. 字符串哈希 视频

时间复杂度 $O(n)$

参考文献

算法基础课

Java 代码

class Solution {
    static int N = 100010;
    static int P = 131;

    static long[] h = new long[N];
    static long[] p = new long[N];//p进制中每个位置对应的值
    static long get(int L,int R)
    {
        return h[R] - h[L - 1] * p[R - L + 1];
    }
    public String longestPrefix(String s) {
        int n = s.length();
        s = " " + s;
        p[0] = 1;
        for(int i = 1;i <= n;i++)
        {
            h[i] = h[i - 1] * P + s.charAt(i);
            p[i] = p[i - 1] * P;
        }
        int len = 0;
        for(int i = 1;i < n;i ++)
        {
            if(get(1,i) == get(n - i + 1,n)) len = i;
        }
        return s.substring(1,len + 1);
    }
}