C++で1をちょうどK個含むバイナリ文字列の部分文字列を数える方法

0と1の組み合わせからなるバイナリ文字列と整数値 k が与えられ、「1をちょうど k 個含む部分文字列」がいくつ作れるかを求めるのが本記事の目的です。

入力例と出力例

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

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

説明 − 与えられた文字列から作れる部分文字列には、1, 10, 100, 1000, 10000, 010, 100001, 10001, 1001, 101, 11, 1000010 などがあります。このうち「1をちょうど2個含む」条件を満たす部分文字列は6個存在します。

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

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

説明 − k = 3 と指定されていますが、元の文字列に含まれる1の総数は2個しかありません。そのため、1を3個含む部分文字列は1つも作れず、答えは0になります。

プログラムで使用するアプローチ

• 0と1の組み合わせからなるバイナリ文字列と、整数変数 k を入力として受け取ります。

• length() 関数を使って文字列の長さを求め、後続の処理のために関数へ渡します。

• k 個の1を含む部分文字列を格納するための一時変数 count と total を0で初期化して宣言します。

• 1の出現回数（累積カウント）を記録するための配列を、文字列長+1 のサイズで宣言し、すべて0で初期化します。さらに配列の先頭要素を1に設定しておきます（これは「まだ1を1つも読んでいない状態」が1回あることを表すためです）。

• FORループを0から文字列の長さまで回します。

• ループ内では total を total + str[i] - '0' として更新し、現在位置までの1の累積個数を追跡します。total >= k となった場合は、count に arr[total - k] を加算します。これにより「1がちょうど k 個多い位置」から始まる部分文字列の数を効率よく数えられます。

• 最後に count を返します。

• 結果を出力します。

コード例

#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

このアルゴリズムは累積和（プレフィックスサム）の考え方を利用しており、全ての部分文字列を実際に生成して数える力まかせの方法（O(n²)以上）と比べ、O(n) の計算量で効率的に答えを求められる点が大きな特徴です。