Problem

给定一个长度为 $n$ 的小写字母串 $s$,定义一个子串的存在值为它的出现次数乘上它的长度。

求 $s$ 中所有回文子串的最大存在值。

$1\leq n\leq3*10^5$。

这个做法需要比较大的空间(256MB),所以洛谷的 125MB 不是很能过。


Solution

结论:不同的回文串个数不超过 $n$。

证明考虑 Manacher 的过程,新回文串一定是右指针向右拓展的时候才可能出现。而拓展的次数是 $n$ 次,所以不同回文串个数不超过 $n$ 。

于是就可以开始乱搞了。

先和 Manacher 一样,两两字符之间插入一个无用字符 #,固定回文串长度是奇数。

不是很想写 Manacher,于是大力哈希二分可以得到以 $i$ 为中心的最长回文串范围 $[i-r,i+r]$。

挨个插入 哈希表 和 Trie 里去判重肯定是会超时的,所以我们考虑再二分出一个 $l$(如果存在),表示 $[i-l,i+l]$ 这一部分已经被找到过了,要插入的部分就是 $(l,r]$。

那么插入到 Trie 的时候再大力顺便把 哈希值&节点编号 插入哈希表,下次插入的时候去哈希表里面找到上次末尾的节点编号再继续往下走就好了。

于是这道题就被我乱搞过了(模拟赛时空间 256MB)。

CODE

最后修改:2021 年 08 月 13 日
如果觉得我的文章对你有用,请随意赞赏