Truy vấn xâu con thứ X theo thứ tự từ điển C++

Cho chuỗi str và Q truy vấn. Mỗi truy vấn cho số X. Tìm xâu con (substring) thứ X nhỏ nhất theo thứ tự từ điển (lexicographical order).

Ví dụ

str = "point"
Tất cả xâu con theo thứ tự từ điển:
i, in, int, n, nt, o, oi, oin, oint, p, po, poi, poin, point, t

Query X=4 → "n"
X=7 → "oi"
X=2 → "in"
X=13 → "poin"

Phương pháp 1: Sinh tất cả xâu con + Sắp xếp O(N² log N)

Phù hợp N ≤ 1000. Sinh tất cả N(N+1)/2 xâu con, lưu vào vector, sort, trả lời truy vấn O(1).

Phương pháp 2: Suffix Array + LCP (Nâng cao)

Xây Suffix Array O(N log N), mảng LCP. Số xâu con bắt đầu tại suffix SA[i] là N - SA[i] - LCP[i]. Duyệt suffix array để tìm xâu con thứ X mà không cần sinh tất cả. Phức tạp O(N log N) tiền xử lý, O(log N) mỗi truy vấn.

Chương trình C++ (Phương pháp 1 - đơn giản)

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

vector getAllSubstrings(const string& s) {
    vector subs;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        string cur;
        for (int j = i; j < n; j++) {
            cur += s[j];
            subs.push_back(cur);
        }
    }
    sort(subs.begin(), subs.end());
    return subs;
}

int main() {
    string str = "point";
    auto subs = getAllSubstrings(str);
    
    int Q = 4;
    int query[] = {4, 9, 5, 15};
    for (int i = 0; i < Q; i++) {
        if (query[i] <= subs.size())
            cout << "Query " << i+1 << ": " << subs[query[i]-1] << endl;
        else
            cout << "Query " << i+1 << ": Out of range\n";
    }
    return 0;
}

Kết quả

Query 1: n
Query 2: oint
Query 3: nt
Query 4: t

Lưu ý

Số xâu con = N(N+1)/2. Với N=10⁵ thì ~5e9 xâu con → không thể sinh tất cả. Cần Suffix Automaton hoặc Suffix Array + LCP cho bài toán lớn.