숨어 있는 회문

길이가 40 이하인 소문자 단어가 주어질 때, 앞과 뒤에서 글자를 지워 남길 수 있는 가장 긴 팰린드롬 부분수열의 길이를 구한다.

보통4동적 계획법문자열구간재귀면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

앞에서 읽어도 뒤에서 읽어도 똑같은 단어를 회문이라고 한다. 예를 들어 mom과 anna는 회문이다. a처럼 글자가 하나뿐인 단어도 회문이다.

단어 하나가 주어진다. 이 단어의 앞쪽과 뒤쪽에서 글자를 지울 수 있다. 남은 부분이 회문이 되도록 지웠을 때 가장 길게 남길 수 있는 길이를 구한다. 이는 단어 안에 들어 있는 가장 긴 회문의 길이와 같다.

입력

첫째 줄에 알파벳 소문자로만 이루어진 문자열이 주어진다. 문자열의 길이는 1 이상 40 이하이다.

출력

주어진 단어에 들어 있는 가장 긴 회문의 글자 수를 출력한다.