\(\text{Manacher}\) 算法是一种用于解决回文串相关问题的算法，相较于 \(\text{KMP}\) 算法更为简单易懂。

前置处理

在介绍 \(\text{Manacher}\) 算法之前，我们需要了解一些基本概念：回文中心和回文半径。此外，回文串还可以分为奇回文串和偶回文串。为了统一处理，我们可以在每两个相邻字符之间插入一个虚拟字符，比如 \(\texttt{\#}\) ，将偶回文串转换为奇回文串，从而使得所有回文串都可以进行一致处理。

此外，对于回文串，我们需要在头尾各加一个 \(\texttt{\#}\) 的原因是什么呢？这个问题将在后文中进行解释。

Manacher算法

\(\text{Manacher}\) 算法可以在 \(O(n)\) 的复杂度下处理出以每个字符（或两个字符之间）为回文中心的最大回文半径 \(rad[]\) 。

该算法的核心思想是利用回文的对称性，通过重复利用已知的信息来优化时间复杂度。具体来说，通过维护一个回文中心和右端点，不断更新回文半径，从而实现线性时间复杂度的处理。

除了中心扩展算法，我们还可以在此基础上进行二分回文半径，结合子串哈希进行比较，将时间复杂度降低到 \(O(n\log n)\) 。

Manacher算法复杂度

该算法的时间复杂度为 \(O(n)\) 。每个字符至多被从它后面暴力扩展到它一次，因此只会进行 \(O(n)\) 次 while 循环。综上，实际复杂度为 \(O(n)\) 。

通过Manacher算法，我们可以高效地解决回文串相关问题，为字符串处理提供了一种高效的解决方案。