Khôi Phục Xâu Từ Hàm Tiền Tố
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề 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
-1nế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$.
Community Discussion