Khôi Phục Xâu Từ Hàm Tiền Tố

Buổi 54 — KMP & Z-function greedy
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho một mảng số nguyên $\pi[0..n-1]$ có độ dài $n$. Hãy tìm xâu $S$ có thứ tự từ điển nhỏ nhất chỉ gồm các chữ cái tiếng Anh viết thường ('a'–'z') sao cho mảng hàm tiền tố (prefix function) KMP của $S$ đúng bằng $\pi$.

Nếu không tồn tại xâu $S$ nào như vậy, in ra -1.

Dữ liệu vào
  • Dòng 1: số nguyên $n$ ($1 \le n \le 10^5$).
  • Dòng 2: $n$ số nguyên $\pi[0], \pi[1], \dots, \pi[n-1]$ ($0 \le \pi[i] < n$).
Dữ liệu ra
  • Xâu $S$ có thứ tự từ điển nhỏ nhất thỏa mãn, hoặc -1 nếu không tồn tại.
Ví dụ
Input Output
5\n0 0 1 2 0 ababb
3\n0 2 0 -1
Giới hạn
  • $1 \le n \le 10^5$.
Draft saved