Description:


顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

Input:


一行由小写英文字母组成的字符串S

Output:


一行一个整数,表示最长双回文子串的长度。

Sample Input:


Sample Output:


题解:


回文子串的题目大部分都是回文自动机Manacher算法

好吧这是Manacher比较简单的题目,求出最长回文半径以后再搞一搞就可以了。

\(r[i]\) 表示以i为右端点的最长回文半径, \(l[i]\) 表示以i为左端点的最长回文半径。

注意用最长回文半径更新一遍 \(l[i]\)\(r[i]\) 以后,对于任意的 \(l[i]\) ,都有 \(l[i] \ge l[i-1]-1\) ,所以还要求一遍 \(max\) ,对于 \(r[i]\) 也是一样的。

然后扫一遍统计答案就可以了~