C++で文字Xを少なくとも1回含むサブ文字列の数

文字列str[]と文字Xが与えられます。目標は、すべてのサブ文字列に少なくとも1回Xが含まれるようにstr[]のサブ文字列を見つけることです。 str [] =” abc''およびX=’a’の場合、「a」を少なくとも1回含む部分文字列は、「a」、「ab」、「abc」です。カウントは3です。

例を挙げて理解しましょう。

入力 − str [] =“ aabccd” X =’c’

出力 −文字Xを少なくとも1回含むサブ文字列の数は− 14

説明 −少なくとも1つの「c」を含む部分文字列は次のようになります：「c」、「c」、「bc」、「cc」、「cd」、「abc」、「bcc」、「ccd」、「aabc」、「 abcc」、「bccd」、「aabcc」、「abccd」、「aabccd」。

入力 − str [] =“ settings” X =’s’

出力 −文字Xを少なくとも1回含むサブ文字列の数は− 14

説明 −部分文字列には、少なくとも1つの「s」が含まれます。「s」、「s」、「se」、「gs」、「set」、「ngs」、「sett」、「ings」、「setti」、「 tings」、「settin」、「ttings」、「setting」、「ettings」、「settings」

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、n文字の文字列のサブストリングの総数はn *（n + 1）/2であることがわかります。

次に、文字列をトラバースし、文字Xの前の文字を一時としてカウントします。 Xが検出されるとすぐに、Xを含む文字列の長さはtemp+1になります。これで、Xを含むサブストリングの数がXになり、残りの文字（長さ-現在のインデックス）X（temp + 1）になります。これを追加してカウントします。ここでtemp=0を更新し、文字列の終わりまで次のXに進みます。最後に、文字Xを少なくとも1回含むサブ文字列の数としてカウントします。

• 文字列strと文字xを取ります。

• 関数sub_x（char str []、int length、char x）は、文字列、その長さ、文字xを受け取り、文字xを少なくとも1回含む部分文字列の数を返します。

• 初期カウントを0とします。str[]の最初のxの前の文字としてtempを最初に0とします。

• str []のすべての可能なサブストリングの数について、初期カウントサイズ*（size + 1）/2を取ります。

• forループを使用してstr[]をi=0からiまでトラバースします。

• str [i]がxでない場合は、最初のxの前に文字としてtempをインクリメントします。

• 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