Background

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.

Problem Description

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))\}$$

Input Format

The first line contains an integer $n$.

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

Output Format

Output a single number, which is the answer.

9
abbbabbba

3

Hint

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