資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告