Description
「快乐前缀」是在原字符串中既是非空前缀也是后缀(不包括原字符串自身)的字符串。
给你一个字符串 s,请你返回它的最长快乐前缀。
如果不存在满足题意的前缀,则返回一个空字符串。
Examples input
level
Examples Output
l
思路
估计出题人也没有想到这道 hard 题被这么多人水过去了,也不知道是不是数据不够强。
那就来说说思路吧~
标准的 KMP 解法
我们知道在 KMP 里 next[i]
代表模式串第 $i$ 个元素之前最长的等值前后缀的长度。
那么,显然这道题的结果就出来了。
class Solution {
public:
int nextval[100005];
string longestPrefix(string s) {
int n = s.length();
int j = -1;
nextval[0] = -1;
for (int i = 0; i <= n;) {
if (j == -1 || s[i] == s[j]) {
nextval[++i] = ++j;
} else
j = nextval[j];
}
// for (int i = 0; i <= n; i++) {
// cout << nextval[i] << " ";
// }
// cout << endl;
return s.substr(0, nextval[n]);
}
};
字符串 hash 做法
字符串 hash 的方法有很多,但本质上我们要很快的求出给定串每个前缀以及每个后缀的 hash 值。
然后遍历时去比较该 hash 值是否相等,若相等则判断此时的前后缀是否等值即可(相当于处理哈希冲突)。
这里我使用了一种 $k$ 进制表示字符串的方法来计算 hash,计算的方法为:
$$ premit[i] = (premit[i – 1] + (s[i] – ‘a’) * k^i) \% mod $$
$$ lstmit[i] = (lstmit[i + 1] * k + s[i] – ‘a’) \% mod $$
其实 premit
与 lstmit
就类似于给定一个十进制数,然后计算某一段前缀以及后缀的值一样。
其中 $k$ 可随意选取,选取的好坏可能会导致不同的哈希冲突率,建议取 $26$ 以上的质数。
其中 $mod$ 也建议取一个大一点的质数。
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int sat = 1e3 + 7;
const double eps = 1e-8;
class Solution {
public:
LL premit[maxn];
LL lstmit[maxn];
LL gethash(int left, int right) {
if (left <= 0) {
return premit[right];
} else {
return lstmit[left];
}
}
void init(const string &s) {
int len = s.length();
premit[0] = s[0] - 'a';
for (int i = 1, sa = sat; i < len; i++, sa = LL(sa) * sat % mod) {
premit[i] =
(premit[i - 1] % mod + (((s[i] - 'a') * 1LL * sa) % mod)) % mod;
}
lstmit[len - 1] = s[len - 1] - 'a';
for (int i = len - 2; i >= 1; i--) {
lstmit[i] = (lstmit[i + 1] * sat % mod + s[i] - 'a') % mod;
}
}
string longestPrefix(string s) {
init(s);
int len = s.length();
for (int i = len - 2; i >= 0; i--) {
if (gethash(0, i) == gethash(len - i - 1, len - 1)) {
if (s.substr(0, i + 1) == s.substr(len - i - 1, i + 1)) {
return s.substr(0, i + 1);
}
}
}
return "";
}
};
Python 无脑暴力
class Solution:
def longestPrefix(self, s: str) -> str:
n = len(s)
for i in range(n - 1, 0, -1):
if s.endswith(s[:i]):
return s[-i:]
return ""
C++17 新特性 string_view 加持下的无脑暴力
class Solution {
public:
string longestPrefix(string s) {
int n = s.size();
std::string_view view = s;
for (int k = n - 1; k >= 1; k--) {
if (view.substr(0, k) == view.substr(n - k, k))
return s.substr(0, k);
}
return "";
}
};
这不是昨天周赛的题嘛~
对的呀,随手发一下