Manacher 算法

定义

Manacher 算法由 Glenn Manacher 于 1975 年提出,能在 O(n) 时间内求出字符串的最长回文子串,优于中心扩展 O(n²) 和一般动态规划做法。

原理

先在字符间插入统一的分隔符(如 #),把奇偶长度回文统一为奇数长度。算法维护当前已知延伸最右的回文的中心 c 与右边界 r,并为每个位置记录回文半径。处理新位置 i 时,先利用它关于 c 的对称点的半径作为下界(不超过 r-i),再尝试继续向外扩展,并按需更新 c 和 r。由于右边界单调右移,总扩展次数为线性。

应用

用于最长回文子串、回文计数等字符串问题,是算法竞赛中的常见工具,也可作为文本分析中回文结构检测的基础。

说明

若只需判断回文或求少量查询,也可用字符串哈希加二分替代,但 Manacher 在专门问题上更直接高效。