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