C11SSTR - String Reconstruction

Giới hạn
  • Thời gian: 3.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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..n], T[2] = S[2..n], T[3] = S[3..n],.. T[n] = S[n..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..k-1] = B[1..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..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..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 <= 20; K = 1;
  • 10% test tiếp theo có N <= 20; K <= 1000;
  • 10% test tiếp theo có N <= 20; K <= 10 12 ;
  • 20% test tiếp theo có N <= 1000; K = 1;
  • 20% test tiếp theo có N <= 1000; K <=1000;
  • 20% test cuối cùng có N <= 1000; K <= 10 12 ;

Example 

Input:
4 2
3 4 1 2
Output:
bdab

Giải thích:
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'

  • Người up: yenthanh132
  • Nguồn bài: VOS Round 23 - Lê Ðôn Khuê