网站建设 麓谷,app要多少钱才能开发,宁波网站制作好公司,wordpress怎么设置关键词1. 题目
「快乐前缀」是在原字符串中既是 非空 前缀也是后缀#xff08;不包括原字符串自身#xff09;的字符串。
给你一个字符串 s#xff0c;请你返回它的 最长快乐前缀。
如果不存在满足题意的前缀#xff0c;则返回一个空字符串。
示例 1#xff1a;
输入#x…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) {vectorint next(s.size()1);calNext(next, s);return s.substr(0,next.back());}void calNext(vectorint next, string s){ //字符串中前缀与后缀的最长匹配长度//next[j]k , 在j之前的子串的最长匹配长度为kint 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, 查看下一个匹配位置elsek next[k];//不匹配, 当前查看的前缀太长, k跳回到上一个可能的匹配位置}}
};
