회문 암호 복호화

어느 비밀 결사는 회문을 이용해 전문을 암호화한다. 회문은 앞에서 읽으나 뒤에서 읽으나 똑같은 문자열이다. MADAM, REVIVER, SUCCUS는 회문이고 ADAM, REVENGE, SOCCER는 회문이 아니다. 이 암호에서는 길이가 1이나 2인 문자열을 회문으로 보지 않는다. 즉 A와 MM은 회문이 아니다.

암호화 방법은 간단하다. 원문 사이사이에 글자를 끼워 넣어서, 회문이 되는 부분수열 중 가장 긴 것이 원문과 같아지도록 만든다. 그래서 암호문을 복호화하려면 가장 긴 회문 부분수열을 뽑아내면 된다. 부분수열은 문자열에서 글자 몇 개를 골라 남은 글자의 순서를 그대로 두고 이어 붙인 문자열이다. 예를 들어 YMAOKDOAMIMHAADAMMA의 가장 긴 회문 부분수열은 길이가 11인 MADAMIMADAM이다.

암호문 여러 개를 받았다. 각각을 복호화하는 프로그램을 작성하라.

입력은 여러 개의 데이터 집합으로 이루어지고, 각 줄이 암호문 하나이다. 암호문은 대문자 알파벳 A부터 Z까지로만 이루어지며 길이는 2000자 이하이다. 줄 수는 따로 주어지지 않고, 입력은 파일의 끝에서 끝난다.

모든 암호문은 가장 긴 회문 부분수열의 길이가 2보다 크다.

각 암호문마다 복호화한 원문을 한 줄에 하나씩 출력한다.

가장 긴 회문 부분수열이 여러 개이면 그중 사전순으로 가장 앞서는 것을 출력한다. 후보의 길이가 모두 같으므로 왼쪽부터 글자를 비교하면 답이 하나로 정해진다.