팰린드롬

알파벳 소문자로만 이루어진 문자열이 주어진다. 부분문자열의 등장값은 그 부분문자열이 문자열에 등장하는 횟수와 부분문자열 길이의 곱이다. 팰린드롬인 부분문자열 가운데 등장값이 가장 큰 값을 출력하는 프로그램을 작성한다.

첫째 줄에 알파벳 소문자(a-z)로만 이루어진 문자열이 주어진다. 문자열의 길이는 300,000 이하이다.

팰린드롬인 부분문자열 중 가장 큰 등장값을 한 줄에 출력한다.

문자열 $s$의 길이를 $|s|$로 나타내자. 부분문자열은 $1 \leq i \leq j \leq |s|$를 만족하는 비어 있지 않은 문자열 $s_i s_{i+1} \ldots s_j$이다. 팰린드롬은 왼쪽에서 오른쪽으로 읽은 결과와 오른쪽에서 왼쪽으로 읽은 결과가 같은 문자열이다. 등장값이 큰 후보는 한 글자가 여러 번 나오는 경우와 긴 팰린드롬이 한 번만 나오는 경우를 함께 고려해야 한다.