조각 복원

시간 제한1초메모리 제한128 MB

요약

겹치는 부분을 맞추어 조각들을 순서대로 이어 붙이고 72자 이내로 줄을 나누어 출력합니다.

난이도: 어려움10점 중 8점
유형: 백트래킹, 문자열 매칭, 그래프
정답자: 아직 제출이 없습니다

문제

정부가 대학을 테마파크로 바꾸려는 비밀 계획이 드러날까 두려워 문서를 전자 shredder에 넣어 겹치는 조각으로 잘랐다. 조각 목록을 읽고 겹치는 부분을 맞춰 원문을 복원하는 프로그램을 작성한다.

입력

여러 문제가 주어진다. 각 문제는 # 한 줄로 끝나는 1에서 20줄의 텍스트 조각으로 이루어진다. 각 줄은 1에서 72자의 출력 가능 문자를 담고, 단어는 공백 하나로 구분된다. #는 문제와 전체 입력의 끝을 표시한다. #는 다른 곳에 나타나지 않는다. 같은 조각이 중복될 수 있다.

출력

각 문제에 대해 모든 입력 조각이 등장하고 인접 조각이 정확히 겹치는 배치로 복원한 텍스트를 출력한다. 한 줄은 72자를 넘지 않으며, 단어 사이 공백에서만 줄을 나눈다. 줄바꿈 시 공백은 출력하지 않는다. 문제 사이에는 빈 줄을 넣지 않는다.

예제1

예제 1

입력

they chose Avant
from the regular text.
For headings, they
stands out nicely from
sans-serif font that stands
Avant Garde, a sans-serif
from the regular text.
#
a b r a
c a d a b r a
#
a b r a
c a d a b r a
r a c
#
#

예상 출력

For headings, they chose Avant Garde, a sans-serif font that
stands out nicely from the regular text.
c a d a b r a
c a d a b r a c