부분문자열 비용의 최댓값

시간 제한2초메모리 제한512 MB

요약

문자열 T가 주어질 때, T의 모든 부분 문자열 S에 대해 (길이 곱하기 등장 횟수)의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 문자열, 정렬, 문자열 매칭, 구현
정답자: 아직 제출이 없습니다

문제

문자열 $T$ 가 주어진다. 문자열 $S$ 에 대해 $L(S)$ 는 $S$ 의 길이, $C(S)$ 는 $T$ 안에서 $S$ 가 등장하는 횟수라고 하고, $S$ 의 비용을 다음과 같이 정의한다.

$F(S) = L(S) \times C(S)$

$T$ 안에서 $S$ 가 등장한다는 것은 $S$ 가 $T$ 의 부분문자열로 나타난다는 뜻이다. 등장 위치는 서로 겹쳐도 되고, 시작 위치가 다르면 다른 등장으로 센다. 예를 들어 $T$ = aaaaa, $S$ = aaa이면 $S$ 는 $T$ 안에서 3번 등장하므로 $F(S) = 3 \times 3 = 9$ 다.

$T$ 의 부분문자열 중에서 비용이 가장 큰 값을 구하라.

입력

첫째 줄에 알파벳 소문자로만 이루어진 문자열 $T$ 가 주어진다. $T$ 의 길이는 1 이상 100,000 이하다.

출력

$T$ 의 모든 부분문자열 $S$ 에 대한 $F(S)$ 의 최댓값을 한 줄에 출력한다.

예제2

예제 1
입력
```
aaaaaa
```
예상 출력
```
12
```
예제 2
입력
```
ab
```
예상 출력
```
2
```