C++で辞書式順序におけるX番目に小さい部分文字列を求めるクエリを解く方法

この記事では、文字列 str と Q 個のクエリが与えられる問題を扱います。各クエリには数値 X が含まれており、C++ を使って「辞書式順序で X 番目に小さい部分文字列」を答えるプログラムを作成するのが課題です。

問題の概要

各クエリに対して、文字列から生成できるすべての部分文字列をアルファベット順（辞書式順序）に並べ替えたとき、X 番目に位置する部分文字列を求める必要があります。

具体例を見て理解しましょう。

入力: str = "point"

Q = 4、query = {4, 7, 2, 13}

出力: n, oi, in, poin

解説

str のすべての部分文字列を辞書式順序に並べると、次のようになります。

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

4番目の部分文字列 → n
7番目の部分文字列 → oi
2番目の部分文字列 → in
13番目の部分文字列 → poin

解決アプローチ

最もシンプルな解法は、まず文字列から生成可能なすべての部分文字列を列挙し、それらをデータ構造に格納したうえで、辞書式順序（アルファベット順）にソートすることです。その後、各クエリの X に対応する要素を構造から取り出して出力すれば、目的の結果が得られます。

部分文字列の格納には vector を使用します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
vector<string> 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)<<" : The "<<query[i]<<"th smallest sub-string lexicographically is "<<substrings[query[i] - 1] << endl;
        return 0;
}

出力結果

Query 1 : The 4th smallest sub-string lexicographically is n
Query 2 : The 9th smallest sub-string lexicographically is oint
Query 3 : The 5th smallest sub-string lexicographically is nt
Query 4 : The 15th smallest sub-string lexicographically is t