LeetCode 1392. 最长快乐前缀（KMP）

Celeste ·

更新时间:2024-09-21

· 830 次阅读

1. 题目

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-happy-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题 暴力法，c++ 17 string_view 解决内存占用问题

class Solution {
public:
    string longestPrefix(string s) {
        string_view sv = s;
        int n = s.size(), i;
        for(i = n-1; i >= 1; --i)
        {
        	if(sv.substr(0,i) == sv.substr(n-i,i))
                break;
        }
        return s.substr(0,i);
    }
};

kmp 字符匹配
类似题目：
POJ 3461 字符串匹配（KMP / 哈希（有推导））

class Solution {
public:
    string longestPrefix(string s) {
        vector next(s.size()+1);
        calNext(next, s);
        return s.substr(0,next.back());
    }
    void calNext(vector &next, string& s)
    {	//字符串中前缀与后缀的最长匹配长度
    	//next[j]=k , 在j之前的子串的最长匹配长度为k
    	int j = 0, k = -1;
    	next[0] = -1;
    	while(j < s.size())
    	{
    		if(k == -1 || s[j] == s[k])
			// 有[0, ..., k-1]与[j-k, ..., j-1] 匹配, 同时 s[j] == s[k]
    			next[++j] = ++k;
    			//匹配长度增加 1, 查看下一个匹配位置
    		else
    			k = next[k];
    			//不匹配, 当前查看的前缀太长, k跳回到上一个可能的匹配位置
    	}
    }
};

在这里插入图片描述