Biến Đổi Burrows-Wheeler Thuận
Đề bài
Trong kỹ thuật nén dữ liệu bzip2, bước tiền xử lý quan trọng nhất là biến đổi Burrows-Wheeler (BWT) nhằm gom các ký tự giống nhau lại gần nhau. Cho một xâu $S$ độ dài $N$ chỉ gồm các chữ cái tiếng Anh in thường. Đầu tiên, ta gắn thêm ký tự kết thúc $ (có thứ tự từ điển nhỏ hơn mọi chữ cái 'a'..'z') vào cuối xâu để thu được xâu $T = S + \text{"\$"}$ có độ dài $N+1$. Sau đó, xét toàn bộ $N+1$ phép xoay vòng của xâu $T$, sắp xếp chúng theo thứ tự từ điển tăng dần, rồi lấy ký tự cuối cùng của mỗi phép xoay vòng theo thứ tự đã sắp xếp để ghép thành xâu kết quả $B$. Hãy tìm xâu $B$.
Dữ liệu vào
Một dòng duy nhất chứa xâu $S$ ($1 \le |S| \le 10^5$) chỉ gồm các chữ cái in thường từ 'a' đến 'z'.
Dữ liệu ra
In ra xâu $B$ có độ dài $N+1$ là kết quả của phép biến đổi Burrows-Wheeler.
Ví dụ
| Input | Output |
|---|---|
| banana | annb$aa |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion