# Leetcode 1392 最长快乐前缀（技巧）

## Description

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

## Examples input

level


## Examples Output

l


## 思路

### 标准的 KMP 解法

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 做法

$$premit[i] = (premit[i – 1] + (s[i] – ‘a’) * k^i) \% mod$$

$$lstmit[i] = (lstmit[i + 1] * k + s[i] – ‘a’) \% 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 "";
}
};


### 2 只已被捕捉

• bestsort Chrome | 80.0.3987.149 Windows 10/11

这不是昨天周赛的题嘛~

• 千千 Chrome | 80.0.3987.106 Windows 10/11

对的呀，随手发一下