【C++入門】バイナリ文字列内の「1」で始まり「1」で終わる部分文字列を数える方法

長さ N のバイナリ文字列 str が与えられたとき、その中に含まれる「1」で始まり「1」で終わる部分文字列の個数を求める問題を考えてみましょう。ここでいうバイナリ文字列とは、「0」と「1」のみで構成された文字列のことです。

具体例

入力例1：

N = 5
str = "11101"

出力：

6

解説：このバイナリ文字列には、「1」で始まり「1」で終わる部分文字列が6つ存在します。具体的には、{"11", "111", "1110", "11101", "1101", "101"} の6つです。

入力例2：

N = 4
str = "0011"

出力：

1

解説：この場合、条件を満たす部分文字列は {"11"} のみで、合計1つとなります。

解き方のアプローチ

与えられた文字列の中から「1」で始まり「1」で終わる部分文字列の数を数えるには、実はすべての部分文字列を調べる必要はありません。この問題は、有名な握手問題（n人の人が集まった場で行われる握手の総数を求める問題）と同じ構造を持っています。

ポイントは次の通りです。文字列に含まれる「1」の個数を k とすると、条件を満たす部分文字列は「開始位置の1」と「終了位置の1」のペアとして選べます。同じ位置同士のペアは許されないため、組み合わせの公式より答えは k × (k − 1) / 2 となります。

アルゴリズムの手順

• 長さ N の文字列を入力として受け取ります。

• 整数型関数 countSubstring(int N, string s) を定義し、文字列の長さと文字列を受け取って条件を満たす部分文字列の個数を返します。

• 文字列全体を走査し、「1」の出現回数をカウントします。

• k × (k − 1) / 2 を計算してペア（部分文字列）の総数を求めます。

• 計算結果を返します。

C++での実装例

#include<iostream>
using namespace std;
int countSubstring(int N, string s){
    int count=0;
    for(int i=0; s[i]!= '\0'; ++i){
        if( s[i]== '1' )
            count++;
    }
    return count*(count-1)/2;
}
int main() {
    int N=5;
    string str= "11101";
    cout<< countSubstring(N,str)<<endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

6

この結果の理由を見てみましょう。文字列 "11101" には「1」が4個含まれているため、count = 4 となります。したがって、条件を満たす部分文字列の総数は 4 × (4 − 1) / 2 = 6 と計算でき、実際の出力と一致します。

この方法なら、文字列を一度走査するだけで答えが求まるため、時間計算量は O(N)、空間計算量は O(1) という非常に効率的なアルゴリズムになります。部分文字列を全列挙する O(N²) 以上の素朴なアプローチと比べて、長い文字列でも高速に処理できるのが大きな利点です。