最长双回文串

时间限制:10s    【提交】    空间限制:128MB

题目描述

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


输入格式

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


输出格式

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


样例输入

baacaabbacabb

样例输出

12

提示

样例说明
从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分,且两者都是回文串。
对于100%的数据,2≤|S|≤10^5

2015.4.25新加数据一组


题目来源

2012国家集训队Round 1 day2