题目描述

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

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

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

样例

示例 1：

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

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

输入：s = "leetcodeleet"
输出："leet"
示例 4：

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

提示：

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

算法1 KMP

时间复杂度 $O(n)$

这题就是求整个字符串的非平凡最长前缀和最长后缀，对应kmp算法中的ne[末尾]数组对应的字符串

C++

class Solution {
public:
    string longestPrefix(string s) {
        int len = s.size() ;
        int ne[len+1] = {0} ;
        ne[0] = -1 ;
        for(int i=1,j=-1;i<len;i++){
            while(j>=0 && s[i] != s[j+1]) j = ne[j] ;
            if(s[i] == s[j+1]) j ++ ;
            ne[i] = j ;
        }

        return s.substr(0,ne[len-1]+1) ;
    }
};

算法2 字符串哈希

时间复杂度 $O(n)$

从最长的非平凡前缀和后缀以此判断是否相等，如果存在相等的，这个就是答案

const int P = 131 ;
const int N = 100010 ;
typedef unsigned long long ULL ;
ULL h[N],p[N] ;
class Solution {
public:

    ULL get(int a,int b){
        return h[b] - h[a-1]*p[b-a+1] ;
    }

    string longestPrefix(string s) {

        int len = s.size() ;
        s = " " + s ;
        p[0] = 1 ;
        for(int i=1;i<=len;i++){
            h[i] = h[i-1]*P + s[i] ;
            p[i] = p[i-1]*P ;
        }
        string res = "" ;
        for(int i=2;i<=len;i++){
            if(get(1,len-i+1) == get(i,len)){
                res = s.substr(i) ;
                break ;
            }
        }

        return res ;
    }
};