class Solution {
public:
string longestPrefix(string s) {
}
};
1392. 最长快乐前缀
「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
给你一个字符串 s，请你返回它的 最长快乐前缀。如果不存在满足题意的前缀，则返回一个空字符串 "" 。
示例 1：
输入：s = "level" 输出："l" 解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。
示例 2：
输入：s = "ababab" 输出："abab" 解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
提示：
1 <= s.length <= 105s 只含有小写英文字母原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-24 23:38:19
func longestPrefix(s string) string {
i, length := 1, 0
lps := make([]int, len(s))
for i < len(s) {
if s[i] == s[length] {
length ++
lps[i] = length
i ++
} else {
if length > 0 {
length = lps[length - 1]
} else {
lps[i] = 0
i ++
}
}
}
return s[:lps[len(s) - 1]]
}
python3 解法, 执行用时: 264 ms, 内存消耗: 21.1 MB, 提交时间: 2023-09-24 23:37:50
class Solution:
def longestPrefix(self, s: str) -> str:
n = len(s)
fail = [-1] * n
for i in range(1, n):
j = fail[i - 1]
while j != -1 and s[j + 1] != s[i]:
j = fail[j]
if s[j + 1] == s[i]:
fail[i] = j + 1
return s[:fail[-1] + 1]
#
def longestPrefix2(self, s: str) -> str:
n = len(s)
prefix, suffix = 0, 0
base, mod, mul = 31, 1000000007, 1
happy = 0
for i in range(1, n):
prefix = (prefix * base + (ord(s[i - 1]) - 97)) % mod
suffix = (suffix + (ord(s[n - i]) - 97) * mul) % mod
if prefix == suffix:
happy = i
mul = mul * base % mod
return s[:happy]
java 解法, 执行用时: 15 ms, 内存消耗: 43.5 MB, 提交时间: 2023-09-24 23:37:13
class Solution {
public String longestPrefix(String s) {
int n = s.length();
long prefix = 0, suffix = 0;
long base = 31, mod = 1000000007, mul = 1;
int happy = 0;
for (int i = 1; i < n; ++i) {
prefix = (prefix * base + (s.charAt(i - 1) - 'a')) % mod;
suffix = (suffix + (s.charAt(n - i) - 'a') * mul) % mod;
if (prefix == suffix) {
happy = i;
}
mul = mul * base % mod;
}
return s.substring(0, happy);
}
// kmp
public String longestPrefix2(String s) {
int n = s.length();
int[] fail = new int[n];
Arrays.fill(fail, -1);
for (int i = 1; i < n; ++i) {
int j = fail[i - 1];
while (j != -1 && s.charAt(j + 1) != s.charAt(i)) {
j = fail[j];
}
if (s.charAt(j + 1) == s.charAt(i)) {
fail[i] = j + 1;
}
}
return s.substring(0, fail[n - 1] + 1);
}
}
cpp 解法, 执行用时: 44 ms, 内存消耗: 19.9 MB, 提交时间: 2023-09-24 23:36:36
class Solution {
public:
// Rabin-Karp 字符串编码
string longestPrefix1(string s) {
int n = s.size();
int prefix = 0, suffix = 0;
int base = 31, mod = 1000000007, mul = 1;
int happy = 0;
for (int i = 1; i < n; ++i) {
prefix = ((long long)prefix * base + (s[i - 1] - 97)) % mod;
suffix = (suffix + (long long)(s[n - i] - 97) * mul) % mod;
if (prefix == suffix) {
happy = i;
}
mul = (long long)mul * base % mod;
}
return s.substr(0, happy);
}
// kmp
string longestPrefix(string s) {
int n = s.size();
vector<int> fail(n, -1);
for (int i = 1; i < n; ++i) {
int j = fail[i - 1];
while (j != -1 && s[j + 1] != s[i]) {
j = fail[j];
}
if (s[j + 1] == s[i]) {
fail[i] = j + 1;
}
}
return s.substr(0, fail[n - 1] + 1);
}
};