C++ 给定一个字符串和一个整数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_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;
}