회문 만들기
면접 대비시간 제한2초메모리 제한512 MB
각 문자열에서 한 글자를 지워 회문이 되는 가장 왼쪽 위치를 찾고, 그런 위치가 없으면 만들 수 없다고 출력한다.
문제
회문은 앞에서 읽어도 뒤에서 읽어도 같은 문자열이다. 소문자로만 이루어진 문자열이 주어질 때, 문자 하나를 정확히 하나만 지워서 회문을 만들 수 있는지 판정한다. 문자를 하나 지우므로 결과 문자열의 길이는 원래 길이보다 1 작다.
입력
입력은 최대 30줄이고, 각 줄에는 소문자 알파벳 3자 이상 30자 이하가 주어진다. 마지막 줄에는 # 하나만 주어지며 이 줄은 처리하지 않는다.
출력
각 줄마다 한 줄씩 답을 출력한다. 문자 하나를 지워 회문을 만들 수 있으면 그 회문을 출력하고, 만들 수 없으면 not possible을 출력한다.
회문이 되는 지우기가 여러 가지일 수도 있다. 예를 들어 madmam에서 d를 지우면 mamam이 되고, 가운데 m을 지우면 madam이 된다. 이런 경우에는 앞에 있는 문자를 지워서 얻은 회문을 출력한다. 즉 지울 위치를 왼쪽부터 차례로 시험해서 처음으로 회문이 되는 결과를 출력한다.