Description:

 

Input:


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

Output:


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

Sample Input:


Sample Output:


题解:


好久没有写过Manacher了,又很久没有调出来QAQ

因为题目中的回文串都是以i和i+1之间为对称轴的,所以Manacher可以不用插入字符。

求出p数组后,发现当 \(x \le y - p[y]\)\(y \le x+frac{p[x]}{2}\) 时可以用 \((y-x+1)\times 4\) 更新答案。

可以用set实现 [摊手]

代码如下: