【Python】バイナリ文字列に含まれる「1」のみの部分文字列を数えるアルゴリズム

バイナリ文字列 s が与えられたとき、「1」だけで構成される部分文字列（substring）の総数を求める問題を考えてみましょう。答えが非常に大きくなる可能性がある場合は、結果を 10⁹+7 で割った余りを返します。

問題の例

たとえば、入力が s = "100111" の場合を考えます。このとき出力は 7 になります。

なぜなら、「1」のみを含む部分文字列は次の 7 つだからです。

• 「1」 × 4つ（各位置にある単独の1）
• 「11」 × 2つ
• 「111」 × 1つ

解法のアプローチ

この問題は、文字列を左から右へ一度走査するだけで解くことができます。ポイントは、「現在位置で終わる『1』のみの部分文字列の数」を累積していくことです。

具体的には、以下の手順に従います。

1. カウンタ a = 0 と count = 0 を初期化します。
2. i を 0 から文字列の長さ - 1 まで繰り返します。
   • s[i] が "0" の場合：a = 0 にリセットします（連続した「1」が途切れたため）。
   • それ以外の場合：a += 1 として連続カウントを増やし、count += a で合計に加算します。
3. 最後に count を返します。

仕組みの解説

このアルゴリズムが正しく動作する理由は、連続する「1」が長さ n のブロックを形成するとき、そのブロックから取り出せる「1」のみの部分文字列は n × (n+1) / 2 個になるためです。変数 a は「現在の位置で終わる部分文字列の数」を表しており、これを毎回加算することで全体の総数が自然に求まります。

計算量は時間・空間ともに効率的で、時間計算量は O(n)、追加の空間計算量は O(1) です。

実装例

以下は Python での実装コードです。

def solve(s):
    a = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "0":
            a = 0
        else:
            a += 1
            count += a
    return count

s = "100111"
print(solve(s))

入力

"100111"

出力

7

まとめ

このように、連続する「1」の長さを追跡しながら累積加算を行うことで、線形時間で「1」のみの部分文字列の総数を効率的に求めることができます。大きな入力に対しても高速に動作するため、競技プログラミングなどでも活用できるテクニックです。