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

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 256MB Input: Output:

Task

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

Input data

The first line will contain the string SS.

Output data

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

Constraints and clarifications

  • 1S1 000 0001 \leq |S| \leq 1 \ 000 \ 000
  • For tests worth 5050 points, we have 1S501 \leq |S| \leq 50.

Example 1

stdin

aaa

stdout

4

Explanation

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

Example 2

stdin

ab

stdout

3

Explanation

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

Log in or sign up to be able to send submissions!