在 C++ 中至少包含一次字符 X 的子字符串的计数

2023-06-21 14:22:02 87

给定一个字符串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(charstr[],intlength,charx)接受一个字符串，它的长度，字符x并返回至少一次包含字符x的子字符串的计数。

以初始计数为0。将temp作为str[]中第一个x之前的字符，最初为0。

对于str[]的所有可能子串的数量，取初始计数size*(size+1)/2。

使用for循环从i=0到i

如果str[i]不是x，则将temp作为第一个x之前的字符递增。

如果str[i]==x则包含x的字符串长度将为temp+1。str[]的剩余字符将是length-i。

所有子串都是(temp+1)*(length-i)。添加这个来计数。现在更新temp=0以进行下一次迭代。

这样做直到到达str[]的末尾。

最后返回计数作为结果。

示例

#include 
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: "<输出结果
如果我们运行上面的代码，它将生成以下输出-
Count of sub-strings that contain character X at least once are: 19

在 C++ 中至少包含一次字符 X 的子字符串的计数

下面程序中使用的方法如下

示例

热门推荐

随机推荐