압축 해제
시간 제한1초메모리 제한1024 MB
Burrows-Wheeler 방식으로 순열된 문자열을 복원한다. 마지막 열에서 정렬된 회전들의 대응 관계를 되짚어 원래 문자열을 얻은 뒤 마침표가 맨 앞에 오도록 회전시킨다.
문제
다음과 같은 방법을 생각해 보자. 문자열을 순열로 바꾸는 방법이다. 먼저 문자열의 서로 다른 모든 회전을 만들고, 그것들을 사전순으로 정렬한 다음, 각 회전의 마지막 글자를 이어 붙여 새 문자열을 만든다.
예를 들어 문자열 "LEIDEN."의 경우, 일곱 개의 회전을 사전순으로 나열하면 다음과 같다(여기서 마침표 '.'는 어떤 글자보다도 앞선다).
.LEIDEN
DEN.LEI
EIDEN.L
EN.LEID
IDEN.LE
LEIDEN.
N.LEIDE
따라서 결과 문자열은 "NILDE.E"가 된다.
얼핏 보면 이 치환은 쓸모없어 보이지만, 흥미로운 성질이 하나 있다. 원래 문자열에 같은 부분 문자열이 많으면(실제 언어에서 그럴 수 있다), 치환 후에 같은 글자가 연속으로 많이 나타난다. 따라서 결과 문자열은 블록 압축에 아주 적합하다. 블록 압축에서는 같은 글자가 연속된 블록을 그 글자와, 그 글자가 몇 번 나타나는지를 나타내는 숫자로 바꾼다. 글자가 한 번만 나타나면 숫자를 붙이지 않는다. 예를 들어 문자열 "AAABCC"는 "A3BC2"로 바뀐다.
이제 여러분의 과제는 이렇게 만들어진 최종 문자열을 원래 문자열로 압축 해제하는 것이다. 다만 문자열을 치환하는 것은 완전히 되돌릴 수 있는 연산이 아니다. 원래 문자열은 회전을 고려하지 않으면 유일하게 결정되지 않는다(즉, 각 회전이 같은 치환 결과를 낳는다). 이를 해결하기 위해 원래 문자열은 대문자 뒤에 마침표('.') 하나가 붙은 형태이며, 이 마침표가 시작 회전을 정한다.
입력
입력의 첫 줄에는 테스트 케이스의 수가 하나 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.
- 압축된 문자열이 한 줄에 주어진다. 이 문자열은 대문자, 숫자, 마침표 하나로 이루어져 있으며, 유효한 블록 압축 문자열이다. 압축된 문자열을 만들어 낸 원래 문자열의 길이는 1,000,000자를 넘지 않는다.
출력
각 테스트 케이스마다 압축 해제된 문자열을 한 줄에 출력한다.