给定一个字符串，求其最长回文（对称）子串的长度。例如输入 "google"，最长回文子串为 "goog"，长度为 4。
回文串以中心为轴对称。中心可能是单个字符（奇数长度），也可能是两个相同字符之间（偶数长度）。遍历每个可能的中心，向两边扩展直到字符不匹配，记录最大长度。时间复杂度 O(n²)，空间 O(1)，工程上常用且易实现。
maxLen = 0。i 作为奇数长度中心，扩展 left=i, right=i。(i, i+1) 作为偶数长度中心（若 s[i]==s[i+1]），扩展 left=i, right=i+1。left>=0 && right，每次扩展更新 maxLen。 maxLen。#include <string>
#include <algorithm>
int longestPalindrome(const std::string &s) {
int n = s.size(), maxLen = 0;
auto expand = [&](int l, int r) {
while (l >= 0 && r < n && s[l] == s[r]) {
maxLen = std::max(maxLen, r - l + 1);
--l; ++r;
}
};
for (int i = 0; i < n; ++i) {
expand(i, i); // 奇数长度
expand(i, i + 1); // 偶数长度
}
return maxLen;
}
若需 O(n) 时间，可使用 Manacher 算法。核心思想：在字符间插入特殊符号（如 #）统一奇偶长度，利用已知回文的对称性避免重复扩展，维护当前最右回文右边界 R 及其中心 C。代码稍长，但模板固定，适合竞赛与高性能场景。
int manacher(const std::string &s) {
std::string t = "#";
for (char c : s) { t += c; t += '#'; }
int n = t.size(), maxLen = 0;
std::vector p(n, 0);
int C = 0, R = 0;
for (int i = 1; i < n - 1; ++i) {
int mirr = 2 * C - i;
if (i < R) p[i] = std::min(R - i, p[mirr]);
while (t[i + p[i] + 1] == t[i - p[i] - 1]) ++p[i];
if (i + p[i] > R) { C = i; R = i + p[i]; }
maxLen = std::max(maxLen, p[i]);
}
return maxLen; // 即原串最长回文长度
}
| 算法 | 时间 | 空间 | 适用场景 |
|---|---|---|---|
| 中心扩展 | O(n²) | O(1) | 面试、中等长度串、代码简洁优先 |
| Manacher | O(n) | O(n) | 超长字符串、竞赛、实时系统 |
"aba"）。最长回文子串是字符串算法的基石问题。中心扩展法凭借极简代码覆盖 90% 面试与工程需求；Manacher 算法则是追求极致性能的利器。理解两者原理，可根据实际数据规模灵活选择。
