12917번 - 문자열 함수 계산

문자열 T가 주어진다. 문자열 S에 대한 비용 함수 F(S) = (S의 길이) × (T에서 S가 등장하는 횟수)로 정의한다.

 T에서 S가 등장한다는 의미는 S가 T의 부분문자열로 존재한다는 의미이다. 예를 들어, T = "aaaaa", S = "aaa"이면, T에서 S가 3번 등장하기 때문에, F(S) = 3 × 3 = 9가 된다. 소문자로만 이루어진 문자열 T가 주어졌을 때, T의 모든 부분문자열 중에서 비용 함수의 값이 최대인 것을 구해보자

첫째 줄에 길이가 10만 이하인 문자열 T가 주어진다.

T의 모든 부분문자열 중에서 비용 함수의 최댓값을 출력한다.