แบบสอบถามเพื่อตอบสตริงย่อยที่เล็กที่สุดลำดับที่ X ใน C ++

ในปัญหานี้ เราได้รับข้อความค้นหาสตริง str และ Q Query แต่ละรายการมีตัวเลข X หน้าที่ของเราคือสร้างโปรแกรมเพื่อแก้ไข Queries เพื่อตอบสตริงย่อยที่เล็กที่สุดลำดับ X ในภาษา C++

คำอธิบายปัญหา

เราจำเป็นต้องค้นหาสตริงย่อย Xth ที่เล็กที่สุดสำหรับแต่ละข้อความค้นหา เช่น จากการเรียงลำดับตามตัวอักษร เราจะต้องหาสตริงย่อย Xth

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล :str =“จุด”

Q =4 ข้อความค้นหา ={4, 7, 2, 13}

ผลลัพธ์: n, oi, ใน, ชี้

คำอธิบาย

สตริงย่อยทั้งหมดของ str เรียงตามลำดับศัพท์คือ−

ผม, ใน, int, n, nt, o, oi, oin, oint, p, po, poi, poin, จุด, t

สตริงย่อยที่ 4 - n

สตริงย่อยที่ 7 - oi

สตริงย่อยที่ 2 - ใน

สตริงย่อยที่ 13 - ชี้

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาง่ายๆ ก็คือการสร้างสตริงย่อยที่เป็นไปได้ทั้งหมดของสตริง จัดเก็บไว้ในโครงสร้างข้อมูล จากนั้นจึงจัดเรียงตามลำดับศัพท์เช่น เรียงตามตัวอักษร จากนั้นสำหรับ X ในแบบสอบถาม เราจำเป็นต้องพิมพ์อาร์เรย์ย่อยที่เกี่ยวข้องจากโครงสร้าง

ในการจัดเก็บสตริงย่อย เราจะใช้เวกเตอร์

ตัวอย่าง

#include ใช้เนมสเปซ std;vector สตริงย่อยเป็นโมฆะ find_SortSubstrings (สตริง s) { int len ​​=s.size (); สำหรับ (int i =0; i  
ผลลัพธ์
 
แบบสอบถาม 1 :สตริงย่อยที่เล็กที่สุดลำดับที่ 4 ตามลำดับคือ nQuery 2 :สตริงย่อยที่เล็กที่สุดลำดับที่ 9 ตามลำดับคือ ointQuery 3 :สตริงย่อยที่เล็กที่สุดลำดับที่ 5 ตามลำดับคือ ntQuery 4 :สตริงย่อยที่เล็กที่สุดลำดับที่ 15 ตามลำดับศัพท์คือ t