manacher算法需将原串预处理为"#a#b#b#a#"形式以统一处理奇偶回文，radius数组存半径（含中心），真实长度为rad[i]-1，原串起始位置为(i-rad[i]+1)/2，边界检查必须严格防止越界。
Manacher算法的核心是预处理字符串
不加#分隔符直接跑原串，90%的实现会越界或漏判偶数长度回文。标准做法是把"abba"变成"#a#b#b#a#"，这样所有回文都变成奇数长度，中心唯一、边界清晰。
常见错误：用string::insert循环插'#'——性能差且容易索引错乱；正确做法是一次性构造新串：
string preprocess(const string& s) {
string t = "#";
for (char c : s) {
t += c;
t += '#';
}
return t;
}- 注意：开头必须加
'#'，否则t[0]为中心时左边界会越界 - 不要用
"" + c + "#"拼接，C++中char转string隐式转换慢 - 如果原串含
'#'，得换其他未出现字符（比如'$'），但一般题目保证ASCII可打印字符，'#'安全
radius数组怎么初始化和更新
vector<int> rad</int>存的是以每个位置为中心的回文半径（含中心），不是“回文长度”。比如"#a#b#b#a#"中，中间'b'对应位置的rad[i]是5，代表覆盖"#a#b#b#a#"这一段——所以真实回文长度是rad[i] - 1。
关键逻辑在“利用回文对称性”：当当前i落在已知最右回文[L, R]内，可先设rad[i] = min(rad[2 * C - i], R - i)，其中C是中心。
立即学习“C++免费学习笔记（深入）”；
- 别忘了后续暴力扩展：
while (i - rad[i] >= 0 && i + rad[i] -
rad[i]++后要立刻更新R和C：只有i + rad[i] - 1 > R时才更新 - 初始化
rad全为1，不是0——每个字符自身就是长度为1的回文
怎么从rad数组还原最长回文子串
原始串下标和预处理串下标有固定映射：预处理串位置i对应原串位置(i - 1) / 2（仅当i为奇数）。所以最长回文在原串中的起始位置是(center - rad[center] + 1) / 2，长度是rad[center] - 1。
常见错误：遍历rad时只比大小，却没记录对应的i；或者用i算起始位置时没考虑整除截断。
- 找最大
rad[i]时，一定要同步记下i值，不能只记数值 - 起始位置公式：
start = (i - rad[i] + 1) / 2—— 这个+1是为了抵消#偏移 - 长度直接取
rad[i] - 1，不用再除2或加减
边界和性能要注意什么
Manacher是O(n)的，但常因边界写错退化成O(n²)。最典型的是扩展循环里没检查i - rad[i]是否>= 0，导致string越界抛异常或静默错误。
- 务必用
size_t要小心：i - rad[i]可能是负数，强制转size_t就变极大正数，访问非法内存 - 测试用例一定要包括空串、单字符、全相同字符（如
"aaaa"）、无回文（如"abcde"） - 如果题目要求返回所有最长回文（不止一个），不能只记第一个最大
rad[i]，得扫完整个数组
真正卡住人的往往不是算法思想，而是预处理串索引和原串索引之间那几行换算——写完一定拿"abccba"手动推一遍i=3到i=6的映射。
