数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定一个字符串和一个整数 k，找到当所有子字符串根据给定条件排序时的第 k 个子字符串
简介
在本教程中，我们将实现一种方法来查找根据某些条件对给定字符串和 k 值的所有子字符串进行排序后的第 k 个子字符串。排序子字符串的条件是子字符串按字母顺序排列，同时按照字母表中每个字符出现的顺序生成子字符串。第一个字母生成其所有子字符串，然后第二个字母生成其所有子字符串，依此类推。考虑一个示例：输入字符串为“abc”，按字母顺序排序的子字符串为“a”、“ab”、“abc”、“b”、“bc”、“c”。预定义 k 的值以生成该第 k 个子字符串。
演示 1
String = “bcd” K = 2
输出
The kth value substring is “bc”
在上面的演示中，输入字符串为“bcd”，k 为 2。在“bcd”中首先出现的字符是“b”，它生成其所有子字符串，然后“c”生成其所有子字符串，最后一个字符是“d”。排序后的子字符串的可能组合为“b”、“bc”、“bcd”、“c”、“cd”、“d”。子字符串的第 k 个值为“bc”。
演示 2
String = “bcd‘ K = 10
输出
No such substring is possible
在上面的演示中，输入字符串为“bcd”，k 值等于 10。任务是使用该字符串生成第 10 个子字符串。排序后的子字符串的可能组合为“b”、“bc”、“bcd”、“c”、“cd”、“d”。不存在第 10 个子字符串。输出为“没有这样的子字符串”。
C++ 库函数
语法
length() : 这是一个字符串类库函数，它返回字符串的长度。字符串长度是字符串中字符的数量。
string_name.length();
vector() : 它是在 C++ 中的动态数组，并在 <vector> 头文件中定义。它为其成员元素提供连续的内存位置。
vector<data_type> vector_name;
size() : 它是在 <std> 头文件中定义的标准库函数。它返回字符串的大小。
string_name.size();
push_back() : 它是 vector 类的成员函数。它用于在插入的 vector 元素的末尾插入另一个元素。
vector_name.push_back(value);
begin() : 它是 vector 类的成员函数，并返回起始元素的指针。
vector_name.begin();
end() : 它是 vector 类的成员函数，并返回最后一个元素的指针。
vector_name.end();
substr() : 它是一个字符串类库函数。它使用输入字符串生成子字符串。它接受两个参数：子字符串的起始值和子字符串的长度。
string_name.substr(pos, length);
算法
获取一个输入字符串，并定义 k 的值。
通过定义起始和结束值来生成所有子字符串。
现在，通过迭代所有生成的子字符串来查找第 k 个子字符串。
如果 k 的值大于子字符串的总数，则中断循环并打印输出。
打印值 k 的子字符串。
示例 1
为了实现查找第 k 个子字符串的问题，我们将使用二分查找。二分查找是一种搜索算法，用于在存储的元素中查找元素。
要存储生成的子字符串，请创建一个字符串数组，该数组从第 x 个字符迭代到子字符串 [x +1]。应用二分查找算法从生成的子字符串中查找第 k 个子字符串。其 C++ 实现为
#include <bits/stdc++.h>
using namespace std;
// function to find the kth substring
void findKSubstring(string s, int l, int k)
{
// Generating all susbtrings
int totalSubstring = (l * (l + 1)) / 2;
// when value of k is greater than total number of substrings
if (k > totalSubstring)
{
printf("No substring is possible at this value of k.");
return;
}
// array to store substrings
int arr_substring[l + 1];
arr_substring[0] = 0;
int t = l;
for (int x = 1; x <= l; x++)
{
arr_substring[x] = arr_substring[x - 1] + t;
t--;
}
// using binary search to find the kth substring
int m = 1;
int i = l;
int startIndex = 0;
while (m <= i)
{
int n = (m + i) / 2;
if (arr_substring[n] > k)
{
startIndex = n;
i = n - 1;
}
else if (arr_substring[n] < k)
m = n + 1;
else
{
startIndex = n;
break;
}
}
int endIndex = l - (arr_substring[startIndex] - k);
// Printing the kth substring
for (int x = startIndex - 1; x < endIndex; x++)
cout <<s[x];
}
// Code controller
int main()
{
string s = "abcd";
int k = 3;
int l = s.length();
findKSubstring(s, l, k);
return 0;
}
输出
abc
示例 2
实现从生成的按字母顺序排序的子字符串中查找第 k 个子字符串的任务。在这种方法中，首先生成所有子字符串并按字母顺序对其进行排序。遍历所有子字符串以查找第 k 个子字符串的索引值。打印结果。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string findSubstring(const string& s, int k)
{
int l = s.length();
vector<string> substrg;
// Generate all possible substrings
for (int x = 0; x < l; x++)
{
for (int y = 1; y <= l - x; y++)
{
substrg.push_back(s.substr(x, y));
}
}
// Sort the substrings in alphabetical order
sort(substrg.begin(), substrg.end());
// Check if k is within the range of substrings
if (k >= 1 && k <= substrg.size())
{
return substrg[k - 1];
}
else
{
return "Value of k is -1";
}
}
int main()
{
string s = "abc"; // Predefined string
int k = 5; // Predefined value for k
// Find the kth substring
string kthSubstr = findSubstring(s, k);
// Display the result
cout << "The kth substring is: " << kthSubstr << endl;
return 0;
}
输出
The kth substring is bc.
结论
我们已经完成了本教程，该教程用于查找排序后的子字符串中的第 k 个子字符串。子字符串按字母顺序排序，以便字母表中首先出现的字母形成其子字符串。下一个字母用于创建子字符串，依此类推。要生成所有子字符串，将使用输入字符串和 k 的值。
我们用两个示例实现了此任务，每个示例都有其自己的逻辑。使用 C++ 库函数来实现问题陈述。
134 次查看
