最长回文前后缀

题目描述

小明特别喜欢回文串，然而回文串太少见了，因此他定义了一个字符串的相同长度的、不相交的前缀和后缀是 “回文前后缀”，当且仅当这个前缀和后缀拼起来是个回文串。那么字符串 $S = c_1c_2c_3, . . . , c_n$ 的 “最长回文前后缀” 的长度$L(S )$ 即为 $arg\ maxxS_{[1,x]} = (S_{[n−x+1,n]})T$ 其中 $S_{[i, j]}$ 表示 $S$ 的一个子串 $c_i，c_{i+1} . . . c_j，S^T$ 表示翻转 $S$ 得到的字符串。

对于一个给定的字符串 $S$，小明希望对其进行改造使得 $L(S′)$ 尽可能大。改造允许将字符串中一个任意长度的子串删除。比如删除 $S = abcdebi\ jbba$ 中的子串 $S_{ [3,5]}$ 后 $S$ 变成了 $abbi\ jbba$。

小明想知道改造后的新字符串 $S′$ 的 “最长回文前后缀” 的长度 $L(S′)$ 最大是多少？

输入格式

输入共 $1$ 行，一个字符串 $S$。

输出格式

输出共 $1$ 行，一个整数表示答案。

样例 #1

样例输入 #1

abcdebijbba

样例输出 #1

3

提示

【样例说明】

如题干中的方案删除 $S_{ [3,5]}$ 后，$S′ = abbi\ jbba，L(S′) = 3$。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，保证 $|S | ≤ 500$。

对于 $100\%$ 的评测用例，保证 $|S | ≤ 500000$，$S$ 仅包含小写字母。