RoAlgo Contest #11 - Back to School 2024 | Perlă

Task

You are given a string $S$, consisting only of lowercase Latin letters. The score of a string $T$ is defined as $k + |T|$, where $k$ is the number of occurrences of $T$ in $S$ as a substring, and $|T|$ is the length of string $T$. Your task is to find and print the maximum possible score of a string $T$ that appears in $S$ as a substring at least once.

Input data

The first line will contain the string $S$.

Output data

The first line will contain a single integer, the maximum score found.

Constraints and clarifications

• $1 \leq |S| \leq 1 \ 000 \ 000$
• For tests worth $50$ points, we have $1 \leq |S| \leq 50$.

Example 1

stdin

aaa

stdout

4

Explanation

An optimal string is $T = \text{aa}$.

Example 2

stdin

ab

stdout

3

Explanation

The only optimal string is $T = \text{ab}$.