부분 문자열

1977년에 파지 ΦX174의 염기 서열이 밝혀진 뒤로 수천 종의 DNA 서열이 해독되어 데이터베이스에 쌓였다. 오늘날 거의 모든 유전체는 샷건 시퀀싱으로 읽는다. 이 방법은 염색체를 통째로 읽지 않고, 길이가 수십에서 수백 염기인 짧은 조각 수천 개의 서열을 만들어 낸다. 조각의 양 끝은 서로 겹치므로, 겹치는 부분을 맞춰 알맞은 순서로 이어 붙이면 원래 서열을 복원한다. 유전체가 클수록 이 조립 작업은 어려워지고, 조립 알고리즘은 생물정보학의 주요 연구 분야다.

이 문제는 조립을 가장 단순하게 줄인 형태다. 길이가 모두 $L$인 문자열 $N$개가 주어진다. 길이가 $L + N - 1$인 문자열 $S$를 찾아라. 주어진 $N$개의 문자열은 모두 $S$의 부분 문자열이어야 하고, 시작 위치는 서로 달라야 한다. $S$의 길이가 $L + N - 1$이므로 길이 $L$인 부분 문자열이 시작할 수 있는 위치는 정확히 $N$개이고, 입력의 각 문자열이 그 위치를 하나씩 차지한다.

입력은 $N$개의 줄로 이루어지고, 각 줄에는 길이가 $L$인 문자열이 하나씩 들어 있다. $N$과 $L$은 따로 주어지지 않는다. 문자열은 영어 대문자와 소문자로만 이루어지며, 대문자와 소문자는 서로 다른 문자로 취급한다. $2 \le N \le 100000$, $2 \le L \le 100000$, $N \times L \le 5 \times 1024 \times 1024$이다. 답이 존재하는 입력만 주어진다.

길이가 $L + N - 1$인 문자열을 한 줄에 출력한다. 이 문자열에서 잘라 낸 길이 $L$짜리 부분 문자열 $N$개가, 중복까지 포함해 입력의 문자열 $N$개와 정확히 같아야 한다. 조건을 만족하는 문자열이 여럿이면 사전순으로 가장 앞서는 하나를 출력한다. 문자는 아스키 코드 값으로 비교하므로 모든 대문자가 모든 소문자보다 앞선다.