数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中包含字符X至少一次的子字符串计数
给定一个字符串str[]和一个字符X。目标是找到str[]的子字符串，使得所有子字符串都至少包含X一次。例如，对于str[]=”abc”和X=’a’，至少包含’a’一次的子字符串是“a”、“ab”、“abc”。计数为3。
让我们通过例子来理解。
输入 − str[] = “aabccd” X=’c’
输出 − 至少包含字符X一次的子字符串计数为− 14
解释 − 包含至少一个’c’的子字符串为：“c”、“cc”、“cd”、“bc”、“bcc”、“ccd”、“abc”、“abcc”、“bccd”、“aabc”、“aabcc”、“abccd”、“aabccd”。
输入 − str[] = “settings” X=’s’
输出 − 至少包含字符X一次的子字符串计数为− 14
解释 − 包含至少一个’s’的子字符串为：“s”, "se", "set", "sett", "setti", "setting", "settings", "gs", "ngs", "ngs", "sett", "tings", "setting", "ettings", "settings"
下面程序中使用的算法如下
在这个算法中，我们知道具有n个字符的字符串的子字符串总数为n*(n+1)/2。
我们现在将遍历字符串并计算字符X之前的字符数作为temp。一旦遇到X，包含X的字符串长度将为temp+1。现在我们有X个包含X的子字符串将是剩余字符（长度-当前索引）X（temp+1）。将此添加到计数中。现在将temp更新为0，并继续进行下一个X，直到字符串结束。最后，我们将计数作为至少包含字符X一次的子字符串的数量。
取一个字符串str和一个字符x。
函数sub_x(char str[],int length,char x)接受一个字符串、它的长度、字符x并返回至少包含字符x一次的子字符串的计数。
将初始计数设置为0。将temp作为str[]中第一个x之前的字符数，初始设置为0。
将初始计数设置为size*(size+1)/2，表示str[]所有可能的子字符串的数量。
使用for循环遍历str[]，从i=0到i<size。
如果str[i]不是x，则将temp递增，表示第一个x之前的字符数。
如果str[i] == x，则包含x的字符串长度将为temp+1。str[]的剩余字符将为length-i。
所有子字符串将为(temp+1) * (length-i)。将此添加到计数中。现在将temp更新为0，用于下一次迭代。
执行此操作直到到达str[]的末尾。
最后返回计数作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
int sub_x(string str, int length, char x){
int count = 0;
int temp = 0;
for (int i = 0; i < length; i++){
if (str[i] == x){
int temp_2 = temp + 1;
count = count + temp_2 * (length - i);
temp = 0;
}
else{
temp++;
}
}
return count;
}
int main(){
string str = "abcabbc";
int length = str.length();
char x = 'a';
cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length,
x);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of sub-strings that contain character X at least once are: 19
250 次浏览
