【bzoj2342】[Shoi2011]双倍回文

2014年12月3日3,9970

Description

 

Input

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

Output

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

Sample Input

16
ggabaabaabaaball

Sample Output

12

HINT

N<=500000

题解

p[i]表示i和i+1为中心的最长回文子串长度/2(str[i-k]=str[i+1+k])。。。

用manacher On计算p数组

题目要求计算w wR w wR的最大长度

枚举x为对称轴。。。实际上对称轴在x到x+1之间,即x是第一个wR的最后一位

举些例子推一推发现len(x+1,y)*4能更新答案,仅当y-p[y]<=x且y<=x+p[x]/2

按照y-p[y]排序一下,递推x的时候将符合1式的y插入set,在set中查找x+p[x]/2的前驱更新答案即可

复杂度On+nlogn

usedtobe提出如果把题目要求改成w wR w。。。这样的话限制应该是y<=x+p[x]且y-p[y]<=x