C++で数字列に含まれる偶数の部分文字列の個数を効率的に求める方法

数字のみで構成された文字列が与えられたとき、その中から作れる「偶数で終わる部分文字列」の個数を求める問題です。まずは具体例を見てみましょう。

入力例と出力例

入力

num = "1234"

出力

6

この文字列から作れる偶数の部分文字列は次の6つです。

2
12
4
34
234
1234

考え方（アルゴリズム）

この問題のポイントは、「偶数かどうかは部分文字列の末尾の数字だけで決まる」という性質を利用することです。ある位置 i の数字が偶数であれば、その位置で終わる部分文字列はすべて偶数になります。位置 i で終わる部分文字列の開始位置は 0〜i の i + 1 通りあるため、答えに i + 1 を加算すればよいことになります。

手順をまとめると以下のようになります。

• 数字列の文字列を用意します。

• カウント用の変数を 0 で初期化します。

• 文字列を先頭から順に走査します。

  • 現在の文字から文字 '0' を引くことで、その桁の数値を取得します。

  • その数値が偶数かどうかを判定します。

  • 偶数であれば、現在のインデックス i に 1 を足した値（i + 1）をカウントに加算します。

• 最後にカウントを返します。

この方法なら二重ループを使わず、O(n) の計算量で効率的に答えを求められます。

C++での実装

以下は、上記アルゴリズムをC++で実装したコードです。

#include<bits/stdc++.h>
using namespace std;
int getEvenSubstringsCount(char str[]) {
    int len = strlen(str), count = 0;
    for (int i = 0; i < len; i++) {
        int currentDigit = str[i] - '0';
        if (currentDigit % 2 == 0) {
            count += i + 1;
        }
    }
    return count;
}
int main() {
    char str[] = "12345678";
    cout << getEvenSubstringsCount(str) << endl;
    return 0;
}

実行結果

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

20

動作の解説

入力 "12345678" の場合、偶数の数字は 2（インデックス1）、4（インデックス3）、6（インデックス5）、8（インデックス7）の4つです。それぞれについて i + 1 を加算すると、2 + 4 + 6 + 8 = 20 となり、実行結果と一致します。このように、各桁を一度だけ調べるだけで偶数部分文字列の総数を求められるため、非常にシンプルかつ高速な解法といえます。