你听说过Manacher算法吗？它有什么特别之处？

Manacher算法——那辆神奇的“马拉车”到底有多离谱？

先说个笑话：有一次我在咖啡馆里写代码， 咖啡味儿冲得我几乎忘记自己在干啥，后来啊键盘上蹦出一行「Manacher」——我瞬间怀疑自己是不是穿越到算法大赛现场了。🤯，原来如此。

一、从“回文”说起——你真的懂回文吗？

回文就是正着读和倒着读一样的字符串，常见的例子像 “abba”、 “level”。但别以为这玩意儿只在童话里出现， 这也行？ 实际项目里它可能是密码校验、DNA序列比对甚至是社交媒体的趣味过滤器。

传统暴力法每次都要把整个字符串翻个遍， 时间复杂度 O— 试试水。 —想象一下你让十万行代码每秒跑两次那就是…算了直接说慢。

二、Manacher登场——谁叫它“马拉车”呢？

从一个旁观者的角度看... 这位神秘的大叔Manacher在1995年搞出了一个线性时间 O 的回文神器。核心思路很简单：把原串每两个字符之间塞一个特殊符号， 再在两端各加一个哨兵，这样奇偶回文都统一成奇数长度。

string s = "abac";
string t = "^#a#b#a#c#$"; // 预处理后

算是吧... 接下来用一个数组 p 记录以 i 为中心的最大回文半径。遍历时维护当前已知最右端点 R 和对应中心 C，利用对称性快速跳过已经计算过的区域。