题目描述

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

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

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