5. 最长回文子串
4 min
题目
解法：Manacher算法
思路
使用 Manacher 算法，通过预处理字符串和中心扩展法来线性求解最长回文子串。
算法的正确性基于回文串的对称性。通过插入特殊字符（#）统一处理奇偶长度回文，利用已计算的回文半径 p[i] 来避免重复计算。当 i 在右边界内时，p[i] 的值可以通过其关于中心点的对称点 p[mirror] 推导而来，因为回文具有对称性。如果对称点的回文范围超出了当前左边界，则 p[i] 只能取到右边界的值，否则可以直接使用对称点的值。然后继续中心扩展。这种方法确保每个字符只被扩展常数次，总体时间复杂度为 O(n)。
- Step 1: 预处理字符串，在字符间插入#，首尾添加不同字符@和%防止越界
- Step 2: 初始化数组p存储每个位置的回文半径，center和right记录当前最右回文的中心和右边界
- Step 3: 遍历处理后的字符串，对每个位置i计算初始p[i]值（若在右边界内则利用对称点信息）
- Step 4: 尝试中心扩展，更新p[i]
- Step 5: 如果扩展后右边界超出当前right，更新center和right
- Step 6: 记录最长回文的长度和中心位置
- Step 7: 根据maxCenter和maxLen从原字符串中提取结果
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
string longestPalindrome(string s) {
if(s.size() < 2) return s;
string ss = "@";
for(auto c:s){
ss += "#";
ss += c;
}
ss += "#%";
vector<int>p(ss.size(),0);
int center = 0;int right = 0;
int maxLen = 0;
int maxCenter = 0;
for(int i = 1; i < ss.size() - 1; i++){
p[i] = i<right?min(right - i,p[2*center - i]):0;
while(ss[i+p[i]+1] == ss[i-p[i]-1])
p[i]++;
if(i + p[i] > right){
center = i;
right = i + p[i];
}
if(p[i] > maxLen){
maxLen = p[i];
maxCenter = i;
class Solution {
public:
string longestPalindrome(string s) {
if(s.size() < 2) return s;
string ss = "@";
for(auto c:s){
ss += "#";
ss += c;
}
ss += "#%";
vector<int>p(ss.size(),0);
int center = 0;int right = 0;
int maxLen = 0;
int maxCenter = 0;
for(int i = 1; i < ss.size() - 1; i++){
p[i] = i<right?min(right - i,p[2*center - i]):0;
while(ss[i+p[i]+1] == ss[i-p[i]-1])
p[i]++;
if(i + p[i] > right){
center = i;
right = i + p[i];
}
if(p[i] > maxLen){
maxLen = p[i];
maxCenter = i;
}
}
return s.substr((maxCenter - maxLen)/2,maxLen);
}
};