「JY/Manacher」

最近（2023.12）学了 Manacher，开个题单集一下题供初学者练习吧。 ### 〇、Manacher 算法介绍 可以上 OI Wiki 看或者 CSDN 上讲得比较好的捏。 ### 一、Manacher 板子和简单变体 - [P3805 【模板】manacher](/problem/P3805)（双倍经验：[P1723 高手过愚人节](/problem/P1723)） 官方板子当然得敲一遍了。 复习的时候可以敲双倍经验。 - [SP7586 NUMOFPAL - Number of Palindromes](/problem/SP7586) 虽然说这题暴力可过，但是可以用这题来巩固理解一下 Manacher。 - [P3501 \[POI2010\] ANT-Antisymmetry](/problem/P3501)（双倍经验：[SP15569 STC02 - Antisymmetry](/problem/SP15569)） 可以发现，我们只要修改一下匹配的方式即可。 一种办法是开一个匹配数组 $mt$，那么 $mt_0=1,mt_1=0,mt_\#=\#,mt_\sim=\sim$。 - [P9606 \[CERC2019\] ABB](/problem/P9606)（三倍经验：[UVA11475 Extend to Palindrome](/problem/UVA11475)、[SP4103 EPALIN - Extend to Palindrome](、problem/SP4103)） 可以发现，我们在跑 Manacher 的时候，如果这个最长回文半径恰好扩展到了字符串右侧，那么我们就可以以当前回文中心作为最终串的回文中心。 而要求最终串长最短，显然地，符合要求的回文中心越靠前，最终的串长越短。因此，跑 Manacher 时，一找到符合要求的回文中心，就可以直接退出来了。 - [P1659 \[国家集训队\] 拉拉队排练](/problem/P1659) 发现如果存在一个长度为奇数 $l$ 的回文串，则必定存在长度为 $l-2,l-4,\cdots,1$ 的同回文中心的回文串。 Manacher 跑一遍之后开桶记下每个回文中心可以得到的最长串长，然后倒序遍历，这样就可以累加上之前的回文串个数了。计算时候快速幂优化即可。 --- ### 二、Manacher 一般变体 - [P4555 \[国家集训队\] 最长双回文串](/problem/P4555) 我们定义「交接点」是可以使双回文串的分成两个回文串的位置。 对于每个双回文串，我们发现其交接点是左侧回文串的末尾、右侧回文串的开头。因此我们记 $l_i$ 为以 $s_i$ 开头的最长回文串长，$r_i$ 为以 $s_i$ 结尾的最长回文串长。 跑一遍 Manacher 记下 $l,r$ 后，还需要更新一次。显然 $l_i=\max\{l_i,l_{i-2}-2\},r_i=\{r_i,r_{i+2}-2\}$。最后答案便是 $\max\{l_i+r_i\}$ 了。 - [P4287 \[SHOI2011\] 双倍回文](/problem/P4287) 首先，有一个性质：长度为 $n$ 的字符串本质不同的回文串不超过 $n$ 个。 简要的证明就是，只要证明在右端点加一个字符最多只会多一个本质不同的回文串。考虑反证，如果多了两个，可以把较短那个沿着较长的那个翻转，然后就在前面出现过了。因此最多只会多一个。 于是只要跑一遍 Manacher，在 $mr$ 更新时，判所有新出现的回文串的前一半是否为回文串就可以了。 - [P1872 回文串计数](/problem/P1872)（双倍经验：[CF17E Palisection](/problem/CF17E)） 虽然说暴力可过，但是用线性做法后双倍经验也能过。 考虑记 $l_i,r_i$ 为 $s_i$ 及其左（右）侧的回文子串个数，然后就相当于在跑 Manacher 时进行区间加一。显然这可以差分处理。最后统计方案数显然就是 $k=\sum\limits_{i=2}^n\left(\sum\limits_{j=1}^{i-1}l_i\right)r_i$，而这里可以给 $l_i$ 作前缀和优化掉。 - [P6216 回文匹配](/problem/P6216) 先跑一遍 KMP 记下 $s_2$ 所有在 $s_1$ 中出现的位置，然后跑 Manacher 记录每个回文串的贡献（这里需要打一下草稿，最后可以推出可以用二次差分进行快的记录。差分的位置也需要推式子，这里建议自己推一推），最后累加答案即可。 --- ### 三、Manacher 较难变体