Biến Đổi Burrows-Wheeler Thuận

Buổi 56 — Suffix Array & LCP sorting Strings
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
string
Submissions
Đề 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.

Draft saved