Description

As drd’s good friend, the tech guy atm gave him a very long string $S$ as a birthday present. atm asks drd to find a longest string $T$ such that $T$ appears in $S$ at least twice, and the secret he wants to tell is hidden in $T$.

Because the string is too long, drd can never find a suitable $T$. So drd asks you to help find the length of this $T$.

Input Format

One line. A string, which is $S$ mentioned in the statement.

Output Format

One line. An integer, representing the length of the longest $T$.

ababa

3

Hint

For $30\%$ of the testdata, the length of $S$ is $\le 100$.

For $60\%$ of the testdata, the length of $S$ is $\le 8000$.

For $100\%$ of the testdata, the length of $S$ is $\le 500000$.

Time limit: 1 second, 256M. Lanqiao Cup 2014, the 5th National Final.

Translated by ChatGPT 5