当前位置:首页 > 字符串 > 正文
BZOJ2342[Shoi2011]双倍回文
2732+

题目大意:双倍回文,除了他是一个回文串以外,他的长度必须是偶数,其左右两半字符串也必须是偶数回文串,现需要求一个字符串的最长双倍回文长度。

Description

Input

输入分为两行,第一行为一个整数,表示字符串的长度,第二行有个连续的小写的英文字符,表示字符串的内容。

Output

输出文件只有一行,即:输入数据中字符串的最长双倍回文子串的长度,如果双倍回文子串不存在,则输出0。

Sample Input

16
ggabaabaabaaball

Sample Output

12

HINT

N<=500000

解题思路

双倍回文,必须以空隙为中心,否则不可能是偶数长度。使用Manacher算法计算出每个空隙的最长回文长度,在计算过程中,边扩展边查看该回文是否双倍回文,如果是就记录最大长度。

如果判断是双倍回文呢?c[i]减1后是4的倍数,即除以4余1;左右两半也是回文,中心是i,回文长度是c[i](奇数),左半串中心是i-c[i]/2,如果左半串是回文就行,即c[i-c[i]/2]>c[i]/2(因为中心是#,c[i]是奇数);为什么还需要判断字符是#呢?看一下这个例子:ababababa,在计算过程中,并不是只看最长的回文串,会看中间过程。

程序实现

About

坚决不Copy代码!

本文标签:,,,

BZOJ2342[Shoi2011]双倍回文:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!