제노시맨틱스

드디어 외계 지성체와의 접촉이 이루어졌다! 프로키온 IV(Procyon IV)에서 방출된 것으로 보이는 메시지의 흐름이 발견되었다. 세계 최고의 외계기호학자(xenosemanticist)들이 집중적으로 연구한 결과, 메시지의 형식에 대해 다음과 같은 확실한 결론에 도달했다.

메시지는 8비트씩 묶인 비트의 흐름이다. 메시지에서 의미를 가지는 부분은 소문자 알파벳에 대응되지만, 그 사이에 다른 문자가 끼어들기도 한다. 글자들은 구분자(spacer) 글자로 나뉘어 단어(word) 를 이룬다. 구분자로 쓰이는 글자는 한 메시지 안에서도 바뀔 수 있으나, 특정 구분자 쌍으로 둘러싸인 단어는 그 구분자 글자를 내부에 포함하지 않는다. 또한 메시지는 개념적으로 어떤 글자와도 일치할 수 있는 조커(joker) 글자(와일드 구분자) 한 쌍으로 양 끝이 둘러싸여 있다.

예를 들어 메시지 조각 xwrxwtx 에는 세 개의 단어 wr, wt, rx 가 들어 있다. wrxwt 는 이 조각에서 단어가 아니다. 만약 이 조각이 메시지의 맨 앞에 나타났다면 xw 와 xwrxw 도 단어가 될 수 있다. 단어 wr 와 rx 는 서로 겹치지만, wt 는 이 조각의 어떤 단어와도 겹치지 않는다.

한 메시지 안에서 같은 단어는 나타날 때마다 동일한 글자들로 이루어지지만, 그 글자들의 순서는 출현마다 다를 수 있다. 즉, 글자의 중복집합(multiset)이 같은 두 출현은 같은 단어이다.

메시지에는 아무 의미도 없는 단어가 많다(영어의 "err", "umm" 따위처럼). 참단어(true word) 란 다음을 모두 만족하는 단어이다.

• 글자 수가 2 이상 250 이하이고,
• 다른 참단어의 어떤 출현과 겹치며(위치를 최소 한 칸 공유하며),
• 메시지 어딘가에서 반복된다(글자 순서가 달라도 되며, 최소 두 번 나타난다).

위 예시에서 wr 나 rw, 그리고 rx 나 xr 가 메시지의 다른 곳에서 단어로 나타난다면 wr 와 rx 는 둘 다 참단어가 된다. wt 는 wt 나 tw 가 메시지의 다른 곳에서 다른 참단어와 겹치며 나타날 때 참단어가 된다.

메시지를 읽어, 각 메시지에 들어 있는 서로 다른 참단어의 목록을 출력하는 프로그램을 작성하라. 각 참단어는 그 첫 출현의 철자로, 단어가 메시지에서 처음 나타나는 순서대로 출력한다. 두 단어의 첫 출현이 서로 겹친다면, 첫 출현이 먼저 끝나는(끝 위치가 더 앞선) 단어를 먼저 출력한다. 메시지의 시작과 끝은 모두 구분자 글자로 간주한다는 점을 잊지 말라. 한 메시지의 글자 수는 최대 1000이다.

입력은 하나 이상의 메시지로 이루어진다. 각 메시지는 하나 이상의 줄로 이루어진다. 각 줄의 길이는 최대 60자이며, 소문자와 그 밖의 문자가 섞여 있다. 어떤 줄의 마지막 문자가 붙임표(-)이면 메시지는 다음 줄로 이어진다. 소문자 a 부터 z 까지를 제외한 모든 문자는 메시지의 일부가 아니다. 입력은 # 하나만으로 이루어진 줄로 끝난다.

각 메시지에 대해, 위에서 설명한 순서대로 참단어를 한 줄에 하나씩 출력한다. 각 메시지의 목록은 \* 하나만으로 이루어진 줄로 끝맺는다.