Manacher 归档 – Charles Wu的博客

MOCK NOIP 20221108 日志

中规中矩的一场模拟赛。

T1 写得实在是太久了……这也是没办法的事情——如果不对转移作压缩优化就没办法过。

T2 有我喜欢的~~马拉车~~ Manacher 算法，是印象里第二次在模拟赛应用。

然后就没时间了。后两题仍然只有暴力分，但最近频繁遇到跟凸包和线性函数相关的题目，这使我发现 T3 跟它相关。在最后一点时间里实现了构建凸包的函数。代码本身没问题，但思路是错误的。

~~这好像是很早以前的译名了。现在它叫《莉可丽丝》。~~

遇见多模式串匹配，自然想到自动机上 DP。但我们发现题目中给定的两个串 sakana chinanago 在任何一个文本串中最多只能匹配其中一个，且匹配位置唯一。于是简单计数 DP 转移，记录当前二者匹配数之差与目前匹配位置即可。

一些~~不应用就过不了的~~优化：

二者数量之差可只记录到 $\frac{n}{15}$ 。 $15$ 是两个串的总长度。
转移时对于 ? s c a o 还有其他字符分类讨论，保证单次转移复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(1)$ 。

时间复杂度 $\bigO(n^2)$ 。（更多…）

唉，还是没有考虑清楚细节。

容易发现，一个双倍回文串必定是一个回文串，同时前半段也是一个回文串。那么在使用Manacher算法求取每个字符对应的最长回文串时，就可以同步更新答案。

但一开始我写出这样的判断：

1
2
3
 // 完成第i个字符的最长回文的更新后
if (len[i] % 4 == 0 && len[i - (len[i] >> 1)] == len[i] / 2)
    ans = max (ans, len[i]);