給定一個字串和一個整數 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++ 庫函式來實現問題陳述。