给定一个字符串 str[] 和一个字符 X。目标是找到 str[] 的子字符串，使得所有子字符串至少包含 X 一次。对于 str[]=”abc '' 和 X='a'，包含 'a' 至少一次的子串是“a”、“ab”、“abc”。计数为 3。
让我们通过例子来理解。
输入- str[] = “aabccd” X='c'
输出- 包含字符 X 至少一次的子字符串的计数是 - 14
说明- 包含至少一个 'c' 的子字符串将是：“c”、“c”、“bc”、“cc”、“cd”、“abc”、“bcc”、“ccd”、“aabc”、 “abcc”、“bccd”、“aabcc”、“abccd”、“aabccd”。
输入- str[] = “设置” X='s'
输出- 包含字符 X 至少一次的子字符串的计数是 - 14
说明- 子字符串至少包含一个 's' 将是：“s”、“s”、“se”、“gs”、“set”、“ngs”、“sett”、“ings”、“setti”、 “丁”，“设置”，“丁”，“设置”，“设置”，“设置”
在这种方法中，我们知道具有 n 个字符的字符串的子串总数为 n*(n+1)/2。
我们现在将遍历字符串并计算字符 X 之前的字符作为临时字符。一旦遇到 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。
对于 str[] 的所有可能子串的数量，取初始计数 size*(size+1)/2。
使用 for 循环从 i=0 到 i<size 遍历 str[]。
如果 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