숨어 있는 회문
면접 대비시간 제한2초메모리 제한512 MB
길이가 40 이하인 소문자 단어가 주어질 때, 앞과 뒤에서 글자를 지워 남길 수 있는 가장 긴 팰린드롬 부분수열의 길이를 구한다.
문제
앞에서 읽어도 뒤에서 읽어도 똑같은 단어를 회문이라고 한다. 예를 들어 mom과 anna는 회문이다. a처럼 글자가 하나뿐인 단어도 회문이다.
단어 하나가 주어진다. 이 단어의 앞쪽과 뒤쪽에서 글자를 지울 수 있다. 남은 부분이 회문이 되도록 지웠을 때 가장 길게 남길 수 있는 길이를 구한다. 이는 단어 안에 들어 있는 가장 긴 회문의 길이와 같다.
입력
첫째 줄에 알파벳 소문자로만 이루어진 문자열이 주어진다. 문자열의 길이는 1 이상 40 이하이다.
출력
주어진 단어에 들어 있는 가장 긴 회문의 글자 수를 출력한다.