数据结构
网络
关系型数据库管理系统 (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 次查看
