어떤 고대 문자열 하나가 발굴되었다. 학자들은 이 문자열에서 글자 몇 개를 (순서를 유지한 채) 골라내어 앞으로 읽으나 뒤로 읽으나 똑같은 회문(palindrome)을 만들고 싶어한다.

문자열 \(S\) 의 부분 수열(subsequence) 중에서 회문이 되는 가장 긴 것의 길이를 구하여라. 부분 수열이란 원래 문자열에서 0개 이상의 글자를 지워서 (남은 글자들의 순서는 그대로 두고) 얻는 문자열을 말한다.

예를 들어 bbabcbcab 의 가장 긴 회문 부분 수열은 babcbab 으로 길이가 7이다.

\(1 \le |S| \le 2{,}000\), \(S\) 는 소문자 알파벳으로만 이루어진다.

첫째 줄에 소문자 알파벳으로만 이루어진 문자열 \(S\) 가 주어진다. (\(1 \le |S| \le 2{,}000\))

가장 긴 회문 부분 수열의 길이를 출력한다.

riseoj 작성

출처 Original