leetcode 1392. 最长快乐前缀
题目如下
数据范围
典型的披着困难外皮的简单题。说到求相同前后缀，显然直接套用kmp算法求next数组的思路就行。
看到题直接秒了
通过代码
class Solution {
public:
string longestPrefix(string s) {
int n = s.size();
vector<int> next(n);
next[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && s[j] != s[i]) {
j = next[j - 1];
}
if (s[j] == s[i])
j++;
next[i] = j;
}
//next[n - 1]就是指这一个串第n - 1处的相同前后缀的长度
return s.substr(0, next[n - 1]);
}
};
