Xếp Hậu Tố

Buổi 56 — Suffix Array & LCP
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho một xâu $S$ chỉ gồm các chữ cái in thường. Hãy xây dựng mảng hậu tố (suffix array) của xâu $S$, tức là mảng các chỉ số bắt đầu của các hậu tố sau khi sắp xếp theo thứ tự từ điển.

Cụ thể, nếu xâu $S$ có độ dài $n$, thì hậu tố thứ $i$ là xâu con $S[i..n-1]$ (đánh số từ 0). Hãy in ra mảng hậu tố của $S$.

Dữ liệu vào

Một dòng chứa xâu $S$ ($1 \le |S| \le 10^5$) chỉ gồm các chữ cái in thường.

Dữ liệu ra

Một dòng chứa $|S|$ số nguyên cách nhau bởi dấu cách, là mảng hậu tố của $S$.

Ví dụ
Input Output
banana 5 3 1 0 4 2
Giới hạn
  • $1 \le |S| \le 10^5$
  • $S$ chỉ gồm các chữ cái latin in thường.
Draft saved