팰린드롬

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

요약

주어진 문자열에서 길이에 등장 횟수를 곱한 값이 가장 큰 팰린드롬 부분 문자열을 구합니다.

난이도: 보통10점 중 7점
유형: 문자열 매칭, 문자열
정답자: 아직 제출이 없습니다

문제

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

입력

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

출력

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

힌트

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

예제6

예제 1
입력
```
abacaba
```
예상 출력
```
7
```
예제 2
입력
```
aaaaa
```
예상 출력
```
9
```
예제 3
입력
```
a
```
예상 출력
```
1
```
예제 4
입력
```
ab
```
예상 출력
```
1
```
예제 5
입력
```
zz
```
예상 출력
```
2
```
예제 6
입력
```
racecar
```
예상 출력
```
7
```