Manacher 算法

简介

Manacher 是一种写法非常简单的用于快速查找字符串中回文串的算法。其时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)，二者均有 \(2\) 倍常数。

使用 Manacher 算法可得到以每个位置（和分割线）为中心的最长回文串。

步骤

见 OI-wiki 。

例题

P4287 [SHOI2011] 双倍回文

如果我们已知了双倍回文的右侧中心点 \(i\)，我们要找到最靠前的中间中心点（下文简称 \(mid\)）。这要求：

• 两个点都是特殊字符#
• 定义 \(i-mid+1=x\)，以 \(i\) 为中心存在一个半径为 \(x\) 的回文串。
• 以 \(mid\) 为中心存在一个半径为 \(2x\) 的回文串，也就是整个双倍回文串自身也是回文串。
• 上述三个限制等价于题目中的描述。

具体实现：在插入了特殊字符后的 manacher 中，一个双倍回文是满足 \(mid+\frac{p_{mid}-1}{2}\ge 1\) 而且 \(mid\ge i-p_{i}\)。使用两个set，一个维护 \(mid+\frac{p_{mid}-1}{2}\)，一个维护 \(mid\) 即可。