C++で最初と最後の文字が同じ部分文字列をカウントします

文字列strが与えられます。目標は、開始文字と終了文字が同じであるstr内のサブストリングの数をカウントすることです。たとえば、入力が「baca」の場合、部分文字列は「b」、「a」、「c」、「a」、「aca」になります。合計5。

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

入力 − str =” abaefgf”

出力 −最初と最後の文字が同じ部分文字列の数は次のとおりです：9

説明 −部分文字列は

“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.

入力 − str =” abcdef”

出力 −最初と最後の文字が同じ部分文字列の数は次のとおりです。6

説明 −部分文字列は−

“a” , “b” , “c”, “d”, “e” ,”f”. Total 6

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

与えられた問題を解決するための複数のアプローチ、すなわちナイーブなアプローチと効率的なアプローチがあります。それでは、最初に素朴なアプローチを見てみましょう。すべての長さの部分文字列を関数check（）に渡します。その部分文字列が同じ文字で開始および終了する場合は、カウントを増やします。

• 文字列strを取ります。長さをstr.size（）として計算します。

• 関数check（string str）は、部分文字列strを受け取り、最初と最後の文字が同じかどうかをチェックします。 （str [0] ==str [length-1]）。 trueの場合、1を返します。

• 関数check_Start_End（string str、int length）は、strとその長さを入力として受け取り、同じ文字で開始および終了するstrのサブストリングの数を返します。

• 初期カウントを0とします。

• 2つのforループを使用してstrをトラバースします。 i=0からi

• すべての長さのsubstr（i、j）を使用して、すべての部分文字列を取得します。各サブ文字列をcheck（）に渡します。 1を返す場合は、カウントをインクリメントします。

• 両方のforループの終わりに、カウントには同じ開始文字と終了文字を持つstrのサブストリングがいくつかあります。

• 目的の結果としてカウントを返します。

効率的なアプローチ

ご覧のとおり、その答えは元の文字列の各文字の頻度によって異なります。

たとえば、「bacba」では、「b」の頻度は2であり、「b」を含むサブストリングは「b」、「bacb」、および「b」です。

これは2+1C2=3です。まず、各文字の頻度を確認し、 ^{（char + 1の頻度）} を追加します。 C ₂ 。

• 文字列strを取ります。長さをstr.size（）として計算します。

• 関数check_Start_End（string str、int length）は、strとその長さを入力として受け取り、同じ文字で開始および終了するstrのサブストリングの数を返します。

• 初期カウント-0を取ります。

• 配列arr[26]を使用して、各文字の頻度を格納します。

• 文字列をトラバースし、頻度を保存しますarr [str [i] =’a’]++。

• 周波数配列arr[26]をトラバースし、周波数arr [i]ごとに、arr [i] *（arr [i] +1）/2を追加します。数える。

• 結果として最終的にはカウントを返します。

例（素朴なアプローチ）

#include <bits/stdc++.h>
using namespace std;
int check(string str){
   int length = str.length();
   if(str[0] == str[length-1]){
      return 1;
   }
}
int check_Start_End(string str, int length){
   int count = 0;
   for (int i = 0; i < length; i++){
      for (int j = 1; j <= length-i; j++){
         if (check(str.substr(i, j))){
            count++;
         }
      }
   }
   return count;
}
int main(){
   string str = "bcbdedfef";
   int length = str.length();
   cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of substrings with same first and last characters are: 13

例（効率的なアプローチ）

#include <bits/stdc++.h>
using namespace std;
#define maximum 26
int check_Start_End(string str, int length){
   int count = 0;
   int arr[maximum] = {0};
   for(int i=0; i<length; i++){
      arr[str[i] - 'a']++;
   }
   for (int i=0; i<maximum; i++){
      count = count + (arr[i]*(arr[i]+1)/2);
   }
   return count;
}
int main(){
   string str = "bcbdedfef";
   int length = str.length();
   cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str,
length);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of substrings with same first and last characters are: 13