C++でK個を含むバイナリ文字列のサブ文字列の数

2進数の文字列、つまり0と1の組み合わせと整数値kが与えられ、タスクは、与えられたk1を持つ与えられた2進数で形成された部分文字列の数を計算することです。

入力 −文字列str =‘10000100000’、k =2

出力 − K個を含むバイナリ文字列の部分文字列の数は− 6

説明 −指定された文字列から形成できる部分文字列は1、10、100、1000、10000、010、100001、10001、1001、101、11、1000010です。したがって、k個の1、つまり正確に2つの部分文字列が6つあります。

入力 −文字列str =‘10000100000’、k =3

出力 −K個を含むバイナリ文字列の部分文字列の数は− 0

説明 − kの整数値は3として与えられ、2進数を含む文字列をチェックすると、2進数しかありません。したがって、部分文字列がk個の1を指定している可能性はありません。

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

• 0と1の組み合わせと整数変数kを持つ2進数の文字列を入力します。

• length（）関数を使用して文字列の長さを計算し、さらに処理するためにデータを関数に渡します。

• k個の部分文字列を格納するために、一時変数のカウントと合計を0として宣言します。

• サイズが1の頻度を文字列の長さに1を加えたものとして格納する配列を宣言し、0で初期化し、配列の最初の要素を1に設定します。

• 0から配列の長さまでループFORを開始します

• ループ内で、totalをtotal + str [i]-‘0’として設定します。 IF total> =kを確認し、countをcount +arr[total-k]として設定します。

• 返品数

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
int sub_k_ones(string str, int length, int k){
   int count = 0;
   int total_1 = 0;
   int arr_fre[length + 1] = {0};
   arr_fre[0] = 1;
   for (int i = 0; i < length; i++){
      total_1 = total_1 + (str[i] - '0');
      if (total_1 >= k){
         count = count + arr_fre[total_1 - k];
      }
      arr_fre[total_1]++;
   }
   return count;
}
int main(){
   string str = "10000100000";
   int length = str.length();
   int k = 2;
   cout<<"Count of substrings of a binary string containing K ones are: "<<sub_k_ones(str, length, k) << endl;
   return 0;
}

出力

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

Count of substrings of a binary string containing K ones are: 6