邢台市网站建设_网站建设公司_原型设计_seo优化

一、问题背景

求最长回文子串（长度），数据规模超大时唯一可行的O(n)算法

二、Manacher 的核心思想

利用回文的对称性，避免重复扩展，从而把所有扩展操作压缩到 O(n)。

三、关键技巧 1：统一奇偶回文

原串： a a a b b a c 处理后：^# a # a # a # b # b # a # c # $

好处：
所有回文长度统一为“奇数”；回文中心永远是一个字符；始末特殊字符避免扩展时超出边界。

四、关键技巧 2：回文半径数组 p[]

p[i] 表示：以 i 为中心，向左右能扩展的最大半径，即为去掉填充字符后回文串的长度。

五、关键变量（运行时维护）

center：当前最右回文的中心
right ：该回文能覆盖到的最右端位置
始终满足：

right=center+p[center]

六、Manacher 的核心步骤

对每个位置 i：
① 计算对称点mirror = 2 * center - i

② 初始化 p[i]
如果 i < right：p[i] = min(right - i, p[mirror])
否则：p[i] = 0

③ 尝试继续向两边扩展

while(t[i+p[i]+1]==t[i-p[i]-1])p[i]++;

④ 更新最右回文

if(i+p[i]>right){center=i;right=i+p[i];}

最长回文子串长度 = max(p[i])