BZOJ2342[Shoi2011]双倍回文
2732+
作者:crxis 发布:2017-12-25 分类:字符串
题目大意:双倍回文,除了他是一个回文串以外,他的长度必须是偶数,其左右两半字符串也必须是偶数回文串,现需要求一个字符串的最长双倍回文长度。
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,在计算过程中,并不是只看最长的回文串,会看中间过程。