APIO2014 回文串

decription

给定一个长度为 \(n\) 的字符串 \(S\)。求其所有回文子串中出现次数乘上长度的最大值。

• \(n\leq 3\times 10^5\)

solution

根据经典结论，长度为 \(n\) 的字符串的本质不同回文子串个数不超过 \(n\) 个，我们可以找出所有本质不同回文子串，然后计算它们的贡献。

找出每个回文中心的最长回文长度可以通过二分和字符串哈希来实现。拿个 set 记录已经出现过的本质不同回文子串的哈希值。因为边界离回文中心远的子串更有可能此前没有出现过，所以可以从二分出来的边界向内遍历，每次在 set 内查是否出现过，没有的话就计算对答案的贡献并加入 set。

容易发现，找出所有本质不同回文子串的时间复杂度是 \(O(n\log n)\) 的。

下面来解决如何计算一个子串在原串中的出现次数。

处理出原串的 SAM 以及每个前缀对应的状态编号，预处理 parent 树的祖先倍增数组。

查询 \(S_{l\dots r}\) 的出现次数时，就从 \(S_{1\dots r}\) 对应的节点开始倍增，直到 \(\text{len}<r-l+1\)。

这么做时间复杂度是 \(O((n+m)\log n)\) 的，空间复杂度是 \(O(n\log n)\)。

于是这题就做完了。

需要注意的是，128 MiB 的空间十分紧张，需要把 SAM 的空间搞成线性的（似乎 map 都卡不过去，我是手写的 treap），然后再卡一卡倍增数组。

这题卡自然溢出。

SHOI 2011 双倍回文 也可以这么做。