String Reconstruction

Xem dạng PDF

Gửi bài giải

Điểm: 1,86 (OI)
Giới hạn thời gian: 4.5s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VOS Round 23 - Lê Ðôn Khuê
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hôm nay chúng ta sẽ sẽ cùng ôn về Suffix Array!!!

Cho ~1~ xâu ~S~ gồm ~n~ kí tự, ta sinh ra ~n~ xâu con của ~S~ là: ~T_{1} = S_{1 \dots n}~, ~T_{2} = S_{2 \dots n}~, ~T_{3} = S_{3 \dots n}~, ..., ~T_{n} = S_{n \dots n}~;

Sau đó ta sẽ sắp xếp ~n~ xâu ~T~ lại theo thứ tự từ điển tăng dần, ~1~ xâu ~A~ được xem là có thứ tự từ điển nhỏ hơn ~B~ nếu tồn tại ~1~ vị trí ~k~ sao cho ~A_{1 \dots k - 1} = B_{1 \dots k - 1}~ và ~A_{k} < B_{k}~;

Cuối cùng ta sẽ xây dựng mảng ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ với ~a_{i} = x~ nếu xâu ~T_{x}~ nằm ở vị trí ~i~ sau khi đã được sắp xếp tăng dần. Mảng ~a~ được gọi là Suffix Array của xâu ~S~.

Ví dụ:

  • Cho xâu ~S =~ 'bcab'.

  • Ta có ~4~ xâu con:

    • ~T_{1} =~ 'bcab'
    • ~T_{2} =~ 'cab'
    • ~T_{3} =~ 'ab'
    • ~T_{4} =~ 'b'
  • Mảng ~T~ sau khi sắp xếp lại theo thứ tự tăng dần là: ~T_{3}~, ~T_{4}~, ~T_{1}~, ~T_{2}~.

  • Vậy ta có Suffix Array ~a~ là: ~3, 4, 1, 2~

Yêu cầu:

  • Cho trước Suffix Array ~a~, và số ~K~. Trong những xâu có Suffix Array ~a~, hãy tìm xâu ~S~ có thứ tự từ điển nhỏ thứ ~K~.
  • Để đơn giản các xâu chỉ bao gồm các kí tự từ 'a' đến 'z'

Chú thích:

  • Với ~S_{i \dots j}~ ~(i < j)~ là xâu con bao gồm các kí tự liên tiếp của ~S~ trong đoạn từ kí tự thứ ~i~ đến kí tự thứ ~j~ (kí tự đầu tiên trong xâu là kí tự thứ ~1)~. Ví dụ với xâu ~S =~ 'abac' thì ~S_{3 \dots 4} =~ 'ac';
  • ~S_{k}~ là kí tự thứ ~k~ của xâu ~S~.
  • ~|S|~ là độ dài của xâu ~S~ hay số lượng kí tự trong xâu ~S~.
  • Nếu ~k > |S|~ thì ~S_{k}~ là một kí tự rỗng, kí tự rỗng được xem là nhỏ hơn bất kì kí tự nào khác

Input

  • Dòng đầu tiên có ~2~ số: ~N~, ~K~ lần lượt là số kí tự và thứ tự từ điển của xâu cần in ra.
  • Dòng thứ ~2~ chứa ~N~ số nguyên phân biệt là dãy ~a_{1}~, ~a_{2}~, ..., ~a_{N}~

Output

  • Gồm xâu kết quả in trên ~1~ dòng duy nhất, chỉ gồm các chữ cái thường từ 'a' đến 'z', trường hợp không có kết quả thì in ra ~- 1~

Giới hạn

  • ~20\%~ test đầu tiên có ~N \le 20~; ~K = 1~;
  • ~10\%~ test tiếp theo có ~N \le 20~; ~K \le 1000~;
  • ~10\%~ test tiếp theo có ~N \le 20~; ~K \le 10^{12}~;
  • ~20\%~ test tiếp theo có ~N \le 1000~; ~K = 1~;
  • ~20\%~ test tiếp theo có ~N \le 1000~; ~K \le 1000~;
  • ~20\%~ test cuối cùng có ~N \le 1000~; ~K \le 10^{12}~;

Sample Input

4 2
3 4 1 2

Sample Output

bdab

Note

3 xâu đầu tiên theo thứ tự từ điển có Suffix Array như đã cho là:

bcab

bdab

beab

~K = 2~ nên kết quả sẽ là xâu 'bdab'


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.