Splitology
면접 대비시간 제한1초메모리 제한1024 MB
소문자로 이루어진 길이 500 이하의 문자열을 두 개의 비어 있지 않은 회문으로 나눌 수 있는지 판단하고, 가능하면 두 회문을 출력합니다.
문제
Yosef는 특이한 사람이다. 그는 문자열을 둘로 나누어 살펴보는 아이디어를 내고, 이를 Splitology라고 이름 붙였다. 왜 문자열을 나누는지는 우리도 모른다. 우리가 Yosef는 특이하다고 말하지 않았던가?
Yosef는 팰린드롬이라는 특정한 종류의 문자열에 관심이 있다. 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다. 예를 들어 "ada", "taat", "radar"는 팰린드롬이다. 반면 "taman"은 뒤에서 읽으면 "namat"이 되므로 팰린드롬이 아니다.
Splitology는 아직 새로운 아이디어라서, Yosef는 문자열을 공집합이 아닌 두 문자열로 나눌 수 있는지, 그리고 나눈 두 문자열이 각각 팰린드롬인지 알아보고 있다.
예를 들어 "malamini"는 "malam"과 "ini"로 나눌 수 있고, 둘 다 팰린드롬이다. "ababab"는 "aba"와 "bab"으로 나눌 수 있고, 둘 다 팰린드롬이다. "ababab"는 "ababa"와 "b"로, 또는 "a"와 "babab"으로도 나눌 수 있다.
Yosef의 친구 Gunawan도 특이한 사람이다. Splitology를 알게 된 그는 "irvinganteng"을 두 팰린드롬으로 나눌 수 있는지 Yosef에게 물었다. 답은 아니다. 이 문자열은 두 팰린드롬으로 나눌 수 없다는 것이 증명되어 있다.
입력
첫 줄에 문자열 S가 주어진다. S는 소문자 알파벳(a-z)으로만 이루어지며, 길이는 2 이상 500 이하이다.
출력
S를 두 팰린드롬으로 나눌 수 없으면 한 줄에 "NO"를 출력한다. 그렇지 않으면 S = A + B를 만족하는 두 팰린드롬 A와 B를 한 줄에 공백 하나로 구분하여 출력한다. 가능한 나눔이 여러 가지이면 그중 아무 쌍이나 출력하면 된다.