資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究權重和小於等於 K 的所有子字串的計數
簡介
在本教程中，我們將討論從給定字串中計算權重和小於等於 K 的子字串的問題。為了實現問題陳述，我們考慮一個字串 S 來生成子字串，以及 k 的一些值。字元權重是預定義的整數值，我們考慮 K 的一些值，例如 2、3 或任何其他值。我們只計算總權重等於 K 值的那些子字串。
字元的權重以兩種不同的方式定義：
當權重以任何順序為字串定義時。
當權重按字母順序從 1 開始定義時。
示例 1
String = "aba" K = 5
輸出
The possible substrings with their weights at most 5 is : 6
解釋
使用輸入字串和 k 的值，我們按字母順序從 1 開始獲取字元的權重。'a' 的權重為 1，'b' 的權重為 2，'c' 的權重為 3，'d' 的權重為 4，依此類推。有 6 個可能的子字串，其權重和小於等於 K。這些子字串如下：
a ab aba b ba a
示例 2
String = "abcd" Weight = "1234" K = 6
輸出
Number of substring with their weight at most 6 are 7.
解釋
在上面的輸入字串中，我們初始化所有字元的權重。k 的值為 6。字串“abcd”的字元權重分別為 1234。有 7 個可能的子字串，其權重和小於等於 k。這些子字串如下：
a ab ab cb bc c d
C++ 庫函式
length() - 它是一個字串類庫函式，定義在標準 C++ 庫中。它返回字串的長度（以位元組為單位）。
string_name.length();
vector - 它是在 C++ 中的動態陣列。它提供了對陣列的簡單且高效的刪除和更新操作。它可以是整數型別或字串型別。
vector<data_type> vector_name;
unordered_set() - 它是在 C++ 中的容器，它隨機儲存元素，沒有任何定義的順序。它有助於快速檢索其儲存的元素。
unordered_set <data_type> unordered_set_name;
演算法
初始化輸入字串。
考慮按字母順序從 1 開始的字元權重。
初始化 k 的值（最大可能的權重）。
遍歷所有權重最大等於 k 的子字串。
計數器變數計算所有權重最大為 k 的子字串。
列印 k 的結果。
示例 1
在這裡，我們使用 C++ 實現問題陳述。使用者定義函式“countSubstrings()”用於計算所有權重和小於等於 K 的子字串。子字串權重從 1 開始，並按字母順序分配。
#include <iostream>
#include <string>
using namespace std;
int countSubstrings(const string& s, int K) {
int cnt = 0;
int l = s.length();
for (int x = 0; x < l; x++){
int sum = 0;
for (int y = x; y < l; y++) {
// Calculate the weight of the substring from index i to j
sum += s[y] - 'a' + 1; // Assuming weights are based on alphabetical order
// If the sum of weights is less than or equal to K, increment the count
if (sum <= K){
cnt++;
}
}
}
return cnt;
}
int main() {
string s = "aba"; // Predefined string
int K = 5; // Predefined maximum weight
int Output = countSubstrings(s, K);
cout << "Count of substrings with sum of weights at most " << K << ": " << Output << endl;
// Generating substrings
cout << "Substrings with sum of weights at most " << K << ":" << endl;
int l = s.length();
for (int x = 0; x < l; x++) {
for (int y = x; y < l; y++){
string substrg = s.substr(x, y - x + 1);
int weight = 0;
for (char ch : substrg){
weight += ch - 'a' + 1;
}
if (weight <= K) {
cout << substrg << endl;
}
}
}
return 0;
}
輸出
Count of substrings with sum of weights at most 5: 6 Substrings with sum of weights at most 5: a ab aba b ba a
示例 2
我們使用 C++ 實現任務。初始化一個字元字串和一個加權字串。加權字串元素用作輸入字串權重。使用巢狀迴圈使用加權字串生成子字串。計算權重和小於等於 K 的子字串。
#include <iostream>
#include <unordered_set>
using namespace std;
//user-defined function to generate the substrings
void generateSubstrings(string s, string weights, int K, unordered_set<string>& substrings){
//taking length of the input string
int l = s.length();
//loop for generating all substrings
for (int x = 0; x < l; x++){
for (int y = 1; y <= l - x; y++) {
string substring = s.substr(x, y);
//Sum variable to calculate the weights
int sumString = 0;
for (char c : substring){
int post = c - 'a';
sumString += weights[post] - '0';
}
//when string sun is less than equal to K, insert the substring
if (sumString <= K){
substrings.insert(substring);
cout << substring << endl;
}
}
}
}
//Code controller
int main(){
//initialize string
string S = "abcd";
//initialize weight variable
string W = "1234";
//initialize value of K
int K = 6;
unordered_set<string> substrings;
//calling function
generateSubstrings(S, W, K, substrings);
cout << "Count of substrings with weights at most " << K << ": " << substrings.size() << endl;
return 0;
}
輸出
a ab abc b bc c d Count of substrings with weights at most 6: 7
結論
在本教程中，我們計算了權重最大為 k 的所有子字串。我們使用兩種不同的方法實現了該任務。在第一種情況下，我們使用加權字串來初始化輸入字串字元的權重。在第二種情況下，權重按字母順序從 1 開始定義。C++ 用於使用巢狀迴圈概念實現這兩種情況。
在編寫 C++ 程式碼以理解問題陳述的需求並計算子字串之前，我們用一些示例演示了該問題。
464 次檢視
