P3805 [Template] Manacher

Given a string $S$ consisting only of lowercase English letters $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$, find the length of the longest palindromic substring in $S$. The length of the string is $n$.

One line containing a string $S$ consisting of lowercase English letters $\texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt z$.

Output a single integer representing the answer.

$1 \le n \le 1.1 \times 10^7$。 Translated by ChatGPT 5