MÃ HÓA BURROWS-WHEELER

Mã hóa Burrows-Wheeler là một thuật toán sử dụng trong nén dữ liệu được phát minh bởi Micheal Burrows and David Wheeler (1994). Xét từ W gồm n chữ cái tiếng Anh in hoa. Thuật toán mã hóa có thể mô tả như sau (Ví dụ với từ BANANA):

Bước 1: Viết thêm vào cuối từ W một ký tự @, xét n+1 hoán vị vòng quanh: BANANA@ ANANA@B NANA@BA ANA@BAN NA@BANA A@BANAN @BANANA

Bước 2: Sắp xếp n+1 hoán vị vòng quanh đó theo thứ tự từ điển: @BANANA A@BANAN ANA@BAN ANANA@B BANANA@ NA@BANA NANA@BA

Bước 3: Viết ra các ký tự cuối của các hoán vị vòng quanh theo đúng thứ tự sau khi đã sắp xếp tạo thành từ mã của W: ANNB@AA

Với một danh sách các từ, mỗi từ chỉ gồm các chữ cái tiếng Anh in hoa, người ta đã mã hóa chúng bằng phương pháp Burrows-Wheeler để được danh sách các từ mã. Nhiệm vụ của bạn là phải giải mã toàn bộ danh sách các từ mã để phục hồi lại danh sách các từ ban đầu.

Dữ liệu: Vào từ file văn bản BWT.INP gồm nhiều dòng, mỗi dòng chứa một từ mã trong danh sách

Kết quả: Ghi ra file văn bản BWT.OUT có cùng số dòng với file dữ liêụ. Trên mỗi dòng ghi kết quả giải mã của từ trên dòng tương ứng với file dữ liệu.

Ràng buộc dữ liệu: Dữ liệu luôn được cho đúng đắn. Các từ trogn file dữ liệu dài không quá 10⁵ ký tự.

File dữ liệu có không quá 20 từ.

BWT.INP	BWT.OUT
YDRTYEESA@ L@LA Y@M SULBRTE@0 DEMSEE@ OS@ RF@A Y@AA	YESTERDAY ALL MY TROUBLES SEEMED SO FAR AWAY

 TEST - CODE