C++で辞書式順序でX番目に小さいサブ文字列に回答するためのクエリ

この問題では、文字列strとQクエリが与えられます。各クエリには番号Xがあります。私たちのタスクは、クエリを解決して、C++で辞書式順序でX番目に小さいサブ文字列に回答するプログラムを作成することです。

問題の説明

各クエリの辞書式順序で最小のX番目の部分文字列を見つける必要があります。つまり、アルファベット順の並べ替えに基づいて、X番目の部分文字列を見つける必要があります。

問題を理解するために例を見てみましょう

入力 ：str =“ point”

Q =4クエリ={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について、構造から対応するサブ配列を出力する必要があります。

サブストリングを格納するために、ベクトルを使用します。

例

#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