Truy vấn để trả lời chuỗi con nhỏ nhất thứ X về mặt từ vựng trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi str và truy vấn Q. Mỗi Truy vấn có một số X. Nhiệm vụ của chúng tôi là tạo một chương trình để giải các Truy vấn để trả lời chuỗi con nhỏ nhất thứ X về mặt từ vựng trong C ++.

Mô tả vấn đề

Chúng tôi cần tìm chuỗi con nhỏ nhất về mặt từ vựng thứ X cho mỗi truy vấn, tức là dựa trên sắp xếp theo thứ tự bảng chữ cái, chúng tôi sẽ phải tìm chuỗi con thứ X.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào :str =“point”

Q =4 truy vấn ={4, 7, 2, 13}

Đầu ra: n, oi, trong, poin

Giải thích

Tất cả các chuỗi con của str theo thứ tự từ vựng là−

i, in, int, n, nt, o, oi, oin, oint, p, po, poi, poin, point, t

Chuỗi con thứ 4 - n

Chuỗi con thứ 7 - oi

Chuỗi con thứ 2 - trong

Chuỗi con thứ 13 - poin

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản sẽ là tạo ra tất cả các chuỗi con có thể có của chuỗi, lưu trữ chúng trong một cấu trúc dữ liệu, sau đó sắp xếp chúng theo thứ tự từ vựng, tức là thứ tự bảng chữ cái. Sau đó, đối với X trong các truy vấn, chúng ta cần in mảng con tương ứng từ cấu trúc.

Để lưu trữ các chuỗi con, chúng tôi sẽ sử dụng vectơ.

Ví dụ

 #include  using namespace std; vector  substrings; void find_SortSubstrings (string s) {int len ​​=s.size (); for (int i =0; i  
 Đầu ra 
 
 Truy vấn 1:Chuỗi con nhỏ thứ 4 về mặt từ vựng là n Câu hỏi 2:Chuỗi con nhỏ thứ 9 về mặt từ vựng là oint Câu hỏi 3:Chuỗi con nhỏ thứ 5 về mặt từ vựng là nt Câu hỏi 4:Chuỗi con nhỏ thứ 15 về mặt từ vựng là t