Dehuff

어떤 데이터 압축 기법은 알파벳의 각 글자를 하나 이상의 비트로 표현하는 가변 길이 이진 코드 표를 만든다. 보통 자주 등장하는 글자에는 드물게 등장하는 글자보다 더 짧은 코드를 배정한다. 예를 들어 A부터 Z까지의 알파벳에서 글자 E는 글자 Q보다 더 많은 단어에 나타나므로, E의 코드가 Q의 코드보다 짧을 것이라고 기대할 수 있다.

알파벳의 각 글자를 적어도 한 번씩 사용한 표본 문자열과 그 표본 문자열 전체의 이진 인코딩이 주어지면, 그 알파벳에 대한 이진 코드 표를 적어도 하나 복원할 수 있다. 예를 들어 알파벳 {A, B, C}의 각 글자를 사용하는 표본 문자열 CAB을 생각하자. CAB의 이진 인코딩이 01011이라면 가능한 코드 표는 다음 하나뿐이다.

• C = 0
• A = 10
• B = 11

모든 코드는 접두 코드(prefix code)이다. 즉, 표 안의 어떤 코드도 다른 코드의 접두사가 될 수 없다(예를 들어 A = 01, B = 011은 A가 B의 접두사이므로 허용되지 않는다). 표본 문자열과 그 이진 인코딩으로부터 이진 코드 표를 복원하는 프로그램을 작성하라. 코드 표가 정확히 하나만 가능하면 그 표를 정렬하여 출력한다. 주어진 자료로부터 둘 이상의 코드 표를 만들 수 있으면 MULTIPLE TABLES를 출력한다. 코드 공간은 항상 남김없이 모두 사용되며, 사용되지 않는 코드는 없다.

첫 줄에는 뒤따르는 데이터 집합의 개수를 나타내는 정수 N이 하나 주어진다. 각 데이터 집합은 두 줄로 이루어진다. 첫 줄은 표본 문자열로, 알파벳에 속한 모든 글자(또는 공백)를 적어도 한 번씩 포함한다. 둘째 줄은 그 표본 문자열의 이진 인코딩이다. 표본 문자열은 대문자와 공백만 포함한다.

각 데이터 집합에 대해 먼저 DATASET #n 형식의 줄을 출력한다. 여기서 n은 1부터 N까지의 데이터 집합 번호이다. 알파벳을 표현하는 코드 표를 둘 이상 만들 수 있으면 다음 줄에 MULTIPLE TABLES를 출력하고 다음 데이터 집합으로 넘어간다. 코드 표가 정확히 하나만 가능하면, 알파벳의 각 글자에 대해 그 글자, 공백, 등호(=), 공백, 그 글자의 이진 코드를 한 줄씩 출력한다. 글자는 ASCII 값의 오름차순으로 나열한다.