Palinilap

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

요약

소문자 문자열에서 한 글자를 바꾸거나 그대로 두었을 때 만들 수 있는 회문 부분 문자열 개수의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 문자열, 동적 계획법, 완전 탐색
정답자: 아직 제출이 없습니다

문제

팰린드롬은 앞에서 읽어도 뒤에서 읽어도 같은 단어다. 예를 들어 a, abba, anavolimilovana는 팰린드롬이다.

표본은 영어 소문자로만 이루어진 길이 1 이상의 문자열이고, 표본의 가중치는 그 부분문자열 중 팰린드롬인 것의 개수다. 같은 단어가 여러 위치에 나타나면 나타난 횟수만큼 따로 센다.

정확히 말하면, 길이가 $n$ 인 표본을 $w$ 라고 하자. 단어 $w_{a,b}$ 는 $w$ 의 $a$ 번째 위치부터 $b$ 번째 위치까지의 문자를 모두 모은 것이다. $w$ 의 가중치는 $w_{a,b}$ 가 팰린드롬이 되는 정수 쌍 $(a, b)$ ( $1 \le a \le b \le n$ )의 개수로 정의한다.

표본 $w$ 가 주어진다. $w$ 를 그대로 두어도 되고, 위치 하나를 골라 그 위치의 글자를 원하는 글자로 바꿔도 된다. 이렇게 해서 얻을 수 있는 가중치의 최댓값을 구하라.

입력

첫째 줄에 표본 $w$ 가 주어진다. $w$ 는 영어 소문자로만 이루어져 있고, 길이는 1 이상 1000 이하다.

출력

얻을 수 있는 가중치의 최댓값을 출력한다.

힌트

입력이 aaaa이면 모든 부분문자열이 이미 팰린드롬이므로 그대로 두는 것이 최적이다.

입력이 baccb이면 두 번째 글자를 c로 바꿔 bcccb를 만들 수 있고, 이때 가중치는 9다.

예제3

예제 1
입력
```
aaaa
```
예상 출력
```
10
```
예제 2
입력
```
baccb
```
예상 출력
```
9
```
예제 3
입력
```
slavko
```
예상 출력
```
7
```