공주와 암호 해독
시간 제한8초메모리 제한512 MB
길이 10 이하의 단어를 최대 10개 받아, 모든 단어를 부분 문자열로 포함하는 가장 짧은 문자열을 찾고, 길이가 같으면 사전순으로 가장 앞선 것을 출력한다.
문제
어느 가난한 나라의 말괄량이 용감한 공주는 신분을 숨기고 나간 마을에서 일본어로 쓰인 고문서를 손에 넣었다. 공주는 일본어를 할 줄 알아서 곧바로 이 고문서를 읽어 보았다. 그러자 놀라운 사실이 드러났다. 이 고문서는 고대의 비보가 있는 곳을 알려 주고 있었다. 그런데 비보의 위치는 암호로 되어 있어 쉽게 알 수 없었다. 그래서 공주는 시종인 당신에게 암호 해독을 돕도록 명령을 내렸다.
당신은 공주를 돕기 위해 밤낮을 가리지 않고 조사했다. 그 결과 Shortest Secret String (SSS)이라는 문자열이 해독에 중요한 역할을 한다는 것을 알아냈다. 여기서 SSS란 N개의 단어 전부를 부분 문자열로 포함하면서 길이가 최소인 문자열이다.
당신의 일은 N개의 단어에서 SSS를 찾아내는 것이다.
입력
입력은 여러 데이터 세트로 주어진다. 데이터 세트의 첫 줄에는 데이터 세트에 포함된 단어의 수 N(1≤N≤10)이 주어진다. 이어지는 N줄에 단어가 주어진다. 마지막 데이터 세트 뒤에는 0만을 포함하는 한 줄이 주어진다.
입력으로 주어지는 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 최대 10임이 보장된다.
출력
각 데이터 세트에 대해 SSS를 한 줄에 출력한다. 여러 개가 있으면 사전 순으로 가장 작은 것을 출력한다.