在C ++中按字典顺序查询第X个最小的子字符串的查询

在这个问题中，我们给了字符串str和Q查询。每个查询都有一个数字X。我们的任务是创建一个程序来解决查询，以C ++的词典顺序回答第X个最小的子字符串。

问题描述

我们需要为每个查询找到第Xth个字典最小的子字符串，即基于字母顺序排序，我们将不得不找到第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

第四子字符串-n

第七子字符串-oi

第二个子字符串-输入

第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