题目就是要求最长的一个子串xyxy,其中y是x的反串。

首先肯定可以想到枚举中间点,然后再算答案。
然后就是中间点固定的情况下如何算。

其实也很简单,最暴力的就是也枚举一个中间点(ans的四等分点)。
然后我们考虑如何优化。

首先,

我们预处理出每个位置作为中间点的最长回文串。

然后,

我们枚举中间点i,然后在i的最长回文串的左四等分点向右找一个最靠前的合法的j作为ans的四等分点。
这边合法的定义就是以j为中心的最长回文串能够盖过i。

如何快速向右找j?
用并查集。
显然在i递增的情况下,j对于i不合法,对于i+1也不合法。

如何求出以i为中心的最长回文串?
可以用sa或sam,不过更好的选择是Manacher算法。优点是好理解(感觉就是暴力优化。。。),好实现,速度快。

代码:

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project