数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中按字典序查找第X小的子字符串的查询
在这个问题中，我们给定一个字符串str和Q个查询。每个查询都有一个数字X。我们的任务是创建一个程序来解决这些查询，以C++语言回答按字典序排列的第X小的子字符串。
问题描述
我们需要为每个查询找到第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，我们需要打印数据结构中对应的子数组。
为了存储子字符串，我们将使用向量。
示例
#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
更新于：2020年10月9日
126 次浏览
广告