string-function-calculation

String Function Calculation ⬀

Задана строка T, рассмотрим некоторую ее подстроку S. Определим функцию f(S):

f(S) = |S| ✕ (КОЛИЧЕСТВО ВХОЖДЕНИЙ S В T)

Ваша задача — посчитать, какое максимальное значение принимает f(S) на множестве всех подстрок строки T.

Формат входных данных

В единственной строке записана строка T, состоящая только из строчных букв латинского алфавита.

Формат выходных данных

Выведите целое число — ответ на задачу.

Ограничения

• 1 ≤ |T| ≤ 10⁵

Пример входных данных #00

aaaaaa

Пример выходных данных #00

12

Примечание #00

f('a') = 6
f('aa') = 10
f('aaa') = 12
f('aaaa') = 12
f('aaaaa') = 10
f('aaaaaa') = 6

Пример входных данных #01

abcabcddd

Пример выходных данных #01

9

Примечание #01

f("a") = 2
f("b") = 2
f("c") = 2
f("ab") = 4
f("bc") = 4
f("ddd") = 3
f("abc") = 6
f("abcabcddd") = 9