P10915 [Lanquiao Cup 2024 National B] Longest Palindromic Prefix-Suffix

Xiaoming especially likes palindromic strings, but palindromic strings are rare. So he defines two non-overlapping prefix and suffix of the same length of a string as a “palindromic prefix-suffix” if and only if concatenating this prefix and suffix forms a palindrome. Then, for a string $S=c_1c_2c_3,\cdots,c_n$, the length $L(S)$ of the “longest palindromic prefix-suffix” is $$ \argmax\limits_{x}{S_{[1,x]} = (S_{[n-x+1,n]})^T} $$ where $S_{[i,j]}$ denotes a substring $c_ic_{i+1}\cdots c_j$ of $S$, and $S^T$ denotes the string obtained by reversing $S$. For a given string $S$, Xiaoming wants to modify it so that $L(S^\prime)$ is as large as possible. The modification allows deleting any substring of arbitrary length from the string. For example, after deleting the substring $S_{[3,5]}$ from $S = \texttt{abcdebijbba}$, $S$ becomes $\texttt{abbijbba}$. Xiaoming wants to know: after the modification, what is the maximum possible value of $L(S^\prime)$ for the new string $S^\prime$?

The input consists of $1$ line, a string $S$.

The output consists of $1$ line, an integer representing the answer.

**Sample Explanation** In the approach described in the statement, after deleting $S_{[3,5]}$, $S^\prime = \texttt{abbijbba}$, and $L(S^\prime) = 3$. **Constraints** For $20\%$ of the testdata, $|S| \le 500$. For $100\%$ of the testdata, $|S| \le 500000$, and $S$ contains only lowercase letters. Translated by ChatGPT 5