ค้นหาซับสตริงที่เล็กที่สุดอันดับ X แบบ Lexicographical ใน C++

ภาพรวมปัญหา

ได้รับสตริง str และ Q คำถาม แต่ละคำถามมีตัวเลข X หาซับสตริงที่เล็กที่สุดอันดับ X เมื่อเรียงตามลำดับเลขโครม (Lexicographical)

ตัวอย่าง

Input: str = "point", Q = 4
Queries: 4, 7, 2, 13
All substrings sorted: i, in, int, n, nt, o, oi, oin, oint, p, po, poi, poin, point, t
Output: n, oi, in, poin

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

• สร้างซับสตริงทั้งหมด O(n²)
• เก็บใน Vector และ Sort แบบ Lexicographical
• ตอบคำถามโดยเข้าถึงดัชนี X-1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

vector substrings;

void find_SortSubstrings(string s) {
    int len = s.size();
    for (int i = 0; i < len; i++) {
        string dup = "";
        for (int j = i; j < len; j++) {
            dup += s[j];
            substrings.push_back(dup);
        }
    }
    sort(substrings.begin(), substrings.end());
}

int main() {
    string str = "point";
    find_SortSubstrings(str);
    int Q = 4;
    int query[] = {4, 9, 5, 15};
    for (int i = 0; i < Q; i++)
        cout << "Query " << i+1 << ": " << substrings[query[i]-1] << endl;
    return 0;
}

ผลลัพธ์

Query 1: 4th smallest substring is n
Query 2: 9th smallest substring is oint
Query 3: 5th smallest substring is nt
Query 4: 15th smallest substring is t