P10271 Long, Quiet Whisper.

> Which page does the story begin from? > > Small stones, red earth, distant fire. > > A groping outline, in the night sky, people who rush into the flames. > > Hands clasping hands, hearts touching hearts. > > Surging deep in the throat, my warm fire.

Some preliminary definitions: - $\text{Rev}(S):$ the string formed by concatenating $S_{|S|}, S_{|S|-1}, \dots, S_1$ in order. That is, reverse $S$. - $\text{lcp}(i,j):$ the **string** that is the longest common prefix of the suffix starting at position $i$ and the suffix starting at position $j$. - $\text{lcs}(i,j):$ the **string** that is the longest common suffix of the prefix ending at position $i$ and the prefix ending at position $j$. - $\text{LCP}(S,T):$ the longest common prefix of $S$ and $T$. ---- Given a string $S$ of length $n$, compute: $$\max\limits_{1 \le i < j \le n}\{\text{LCP}(\text{Rev}(\text{lcs}(i,j)),\text{lcp}(i,j))\}$$

The first line contains an integer $n$. The second line contains a string $S$ of length $n$.

Output a single number, which is the answer.

### Explanation of Sample 1 $\text{lcp}(3,7):$ `bba`. $\text{lcs}(3,7):$ `abb`. $\text{LCP}(\text{Rev}(\texttt{\color{blue}abb}),\texttt{\color{blue}bba}):$ `bba`. It can be proven that there is no better choice than $i=3, j=7$. ### Constraints For $30\%$ of the testdata, $1 \le n \le 2\times 10^3$. For $60\%$ of the testdata, $1 \le n \le 10^5$. For the other $10\%$ of the testdata, $\forall 1 \le i \le n-2, S_{i}\not=S_{i+2}$. For $100\%$ of the testdata, $1 \le n \le 10^6$, and the input consists only of integers and lowercase letters. Translated by ChatGPT 5