C++で別の特定の文字列から構築できる文字列の出現回数をカウントします

入力として2つの文字列str_1とstr_2が与えられます。目標は、各文字が1回だけ使用されるstr_1から選択された文字を使用して構築できるstr_2と同じ文字列の数を見つけることです。

注 −両方のアルファベットはすべて同じ大文字小文字です。

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

入力 − str_1 ="abcaaaabca"、str_2 ="bca";

出力 −別の特定の文字列から構築できる文字列の出現回数は次のとおりです。2

説明 −str_aの部分文字列bca−

str_1[1-3]=”bca” and str[7-9]=”bca”

入力 − str_1 ="about"、str_2 ="cout";

出力 −別の指定された文字列から構築できる文字列の出現回数は− 0

説明 −部分文字列coutはstr_aに存在しません。

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

まず、str_1のすべてのアルファベットの頻度を計算し、それを配列arr_1 [26]に格納し、すべてのアルファベットの頻度を配列arr_2[26]のarr_2に格納します。

• 2つの文字列str_1とstr_2を取ります。長さをstr_1.size（）およびstr_2.size（）として計算します。

• 関数count_string（string str_1、int len_str_1、string str_2、int len_str_2）は、文字列と長さの両方を取り、str_1から構築できる文字列str_2の数を返します。

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

• str_1の文字の頻度については2つの配列arr_1[26]を初期化し、arr_2の文字の頻度についてはarr_2[26]を0で初期化します。

• forループを使用してstr_1とstr_2の両方をトラバースし、arr_1とarr_2の頻度を更新します。

• ここで、forループを使用してarr_2を再度トラバースし、現在の頻度arr_2 [i]がゼロ以外の場合、count（前の値）とarr_1 [i] / arr_2 [i]の最小値（str_2の各文字に対してstr_1から各アルファベットを1回だけ取得） 。

• 最終的に、countには、str_1とstr_2の一致する対応する文字の最小値が含まれます。例aaabbbb（a =3、b =4）およびabb（a =1、b =2）の最小カウントは1になります

• 目的の結果として、すべてのループの最後にカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int count_string(string str_1, int length_str_1, string str_2, int length_str_2){
   int count = INT_MAX;
   int arr_1[26] = { 0 };
   int arr_2[26] = { 0 };
   for (int i = 0; i < length_str_1; i++){
      arr_1[str_1[i] - 'a']++;
   }
   for (int i = 0; i < length_str_2; i++){
      arr_2[str_2[i] - 'a']++;
   }
   int total_alphabets = 26;
   for (int i = 0; i < total_alphabets; i++){
      if(arr_2[i]){
         count = min(count, arr_1[i] / arr_2[i]);
      }
   }
   return count;
}
int main(){
   string str_1 = "knowledge", str_2 = "know";
   int length_str_1 = str_1.size();
   int length_str_2 = str_2.size();
   cout<<"Count occurrences of a string that can be constructed from another given string are: "<<count_string(str_1,length_str_1, str_2, length_str_2);
   return 0;
}

出力

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

Count occurrences of a string that can be constructed from another given string are: 1