Xâu con thứ k theo thứ tự từ điển

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một xâu $s$ chỉ gồm các chữ cái latin in thường. Liệt kê tất cả các xâu con liên tiếp (substring) của $s$ — bao gồm cả các xâu con trùng nhau (ví dụ, xâu $s =$ "aab" có sáu xâu con: "a", "a", "aa", "ab", "aab", "b") — rồi sắp xếp chúng theo thứ tự từ điển.

Cho số nguyên dương $k$ . Hãy in ra xâu con thứ $k$ trong danh sách đã sắp xếp. Nếu tổng số xâu con nhỏ hơn $k$ , hãy in ra dòng No such line. (không có dấu nháy).

So sánh thứ tự từ điển: xâu $x$ nhỏ hơn xâu $y$ nếu hoặc $x$ là tiền tố thực sự của $y$ , hoặc tồn tại vị trí $i$ đầu tiên mà $x_{i} < y_{i}$ .

Dữ liệu vào

Dòng đầu chứa xâu $s$ không rỗng gồm các chữ cái latin in thường.
Dòng thứ hai chứa số nguyên $k$ .

Dữ liệu ra

In ra xâu con thứ $k$ theo thứ tự từ điển, hoặc dòng No such line. nếu không tồn tại.

Ràng buộc

$1 \leq | s | \leq 10^{5}$
$1 \leq k \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
aa 2	a	Các xâu con đã sắp xếp: "a", "a", "aa". Thứ hai là "a".
abc 5	bc	Các xâu con đã sắp xếp: "a", "ab", "abc", "b", "bc", "c". Thứ năm là "bc".
abab 7	b	Các xâu con đã sắp xếp: "a", "a", "ab", "ab", "aba", "abab", "b", "b", "ba", "bab". Thứ bảy là "b".
codeforces 1	c	Xâu con nhỏ nhất theo thứ tự từ điển là "c" (do bắt đầu bằng 'c').

Bình luận

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