[国家集训队] 最长双回文串

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

baacaabbacabb

输出样例 #1

12

说明

**样例说明** 从第二个字符开始的字符串 `aacaabbacabb` 可分为 `aacaa` 与 `bbacabb` 两部分,且两者都是回文串。 **数据范围** 对于 $100\%$ 的数据,$2\leq |S|\leq 10^5$。 2018.12.10,2018.12.15:感谢 @Ycrpro 提供 hack 数据两组。