原文链接: https://leetcode-cn.com/problems/longest-happy-prefix

英文原文

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s, return the longest happy prefix of s. Return an empty string "" if no such prefix exists.

 

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".

Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.

Example 3:

Input: s = "leetcodeleet"
Output: "leet"

Example 4:

Input: s = "a"
Output: ""

 

Constraints:

• 1 <= s.length <= 105
• s contains only lowercase English letters.

中文题目

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

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

通过代码

高赞题解

字符串 Hash

对一个字符串进行 hash 预处理后，就可以在 $O(1)$ 的时间复杂度内判断该字符串的任意两个子串是否相等。

下图讲解来自《算法竞赛进阶指南-李煜东》

代码

typedef unsigned long long ULL;
class Solution {
public:
    string longestPrefix(string s) {
        int base = 131;
        ULL p[100002]; 
        p[0] = 1;
        ULL hash[100002]; 
        hash[0] = 0;
        for (int i = 1; i <= s.size(); i ++) {
            hash[i] = hash[i-1] * base + s[i-1] - 'a' + 1;
            p[i] = p[i-1] * base;
        }
        for (int i = s.size() - 1; i >= 1; i --) {
            ULL pre = hash[i];
            ULL suf = hash[s.size()] - hash[s.size()-i] * p[i];
            if (pre == suf) {
                return s.substr(0, i);
            }
        }
        return "";
    }
};

最后

感谢您的观看！欢迎大家留言，一起讨论交流！

统计信息

通过次数	提交次数	AC比率
8465	20645	41.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言