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

题目描述

顺序和逆序读起来完全一样的串叫做回文串。比如`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≤|S|≤10^5$ 2018.12.10、2018.12.15 感谢 @Ycrpro 提供 hack 数据两组