C++で8の倍数かつ3の倍数ではない部分文字列の個数を数える方法

0〜9の数字だけで構成された文字列が与えられたとき、「8で割り切れるが、3では割り切れない」部分文字列がいくつあるかを求めるのが本記事のテーマです。一見複雑に思えますが、問題を「8の倍数の判定」と「3の倍数の除外」という2つのステップに分けて、一段階ずつコードを組み立てれば解決できます。

入出力例

入力:

str = "80"

出力:

2

この場合、"8" と "80" の2つが条件を満たします。

入力:

str = "7675636788"

出力:

4

こちらは "8"（2か所）、"56"、"88" の合計4つが該当します。

解法のアプローチ

まず押さえておくべき重要な性質は次の2つです。

• 整数が8で割り切れるかどうかは、下3桁だけで判定できます。つまり、長さ3以上の部分文字列が8の倍数かどうかは、末尾3桁が8の倍数かどうかだけで決まります。
• 整数が3で割り切れるかどうかは、各桁の数字和を3で割った余り（0・1・2）で判定できます。

そこで、先頭から各位置までの桁和の累積値を3で割った余り（0,1,2）を前計算して保存しておきます。さらに、dp[i][j] を「位置iまでの接頭辞のうち、桁和を3で割った余りが j となるものの個数」と定義した、サイズ |S|×3 の二次元配列を用意します（|S| は文字列の長さ）。ここで j は 0 ≤ j ≤ 2 の範囲を取ります。

続いて文字列を走査し、各位置 i を右端とする長さ1桁・2桁・3桁の数が8で割り切れるかを順番にチェックしていきます。

• 1桁の場合： その位置の文字が '8' であればカウントします（8は3の倍数ではないため、そのまま答えに加算できます）。
• 2桁の場合： 直前の文字と組み合わせた2桁の数を作り、それが8で割り切れ、かつ3で割り切れない場合にカウントします。
• 3桁の場合： 末尾3桁が8の倍数であれば、位置 i を右端とする長さ3以上のすべての部分文字列が8の倍数になります。ただしその中には3の倍数でもあるものが含まれるため、dp配列を参照して該当する個数を差し引きます。

このように「8の倍数の候補を数える」→「3の倍数を除外する」という2段階の処理を行うことで、すべての部分文字列を実際に列挙することなく答えを求められます。計算量は文字列長を n とすると O(n) で、非常に効率的です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

#define MAX 1000
int count (char s[], int len) {
    int cur = 0,
    dig = 0;
    int sum[MAX], dp[MAX][3];
    memset (sum, 0, sizeof (sum));
    memset (dp, 0, sizeof (dp));
    dp[0][0] = 1;
    for (int i = 1; i <= len; i++) {
        dig = int (s[i - 1]) - 48;
        cur += dig;
        cur %= 3;
        sum[i] = cur;
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        dp[i][2] = dp[i - 1][2];
        dp[i][sum[i]]++;
    }
    int ans = 0, dprev = 0, value = 0, dprev2 = 0;
    for (int i = 1; i <= len; i++) {
        dig = int (s[i - 1]) - 48;
        if (dig == 8) ans++;
        if (i - 2 >= 0) {
            dprev = int (s[i - 2]) - 48;
            value = dprev * 10 + dig;
            if ((value % 8 == 0) && (value % 3 != 0)) ans++;
        }
        // 3桁の数を処理
        if (i - 3 >= 0){
            dprev2 = int (s[i - 3]) - 48;
            dprev = int (s[i - 2]) - 48;
            value = dprev2 * 100 + dprev * 10 + dig;
            if (value % 8 != 0) continue;
            ans += (i - 2);
            ans -= (dp[i - 3][sum[i]]);
        }
    }
    return ans;
}
int main () {
    char str[] = "7675636788";
    int len = strlen (str);
    cout << count (str, len) << endl;
    return 0;
}

出力

4

まとめ

本記事では、文字列中に含まれる「8で割り切れるが3では割り切れない」部分文字列の個数を求める方法を、C++のコードとともに解説しました。「下3桁による8の倍数判定」と「桁和の累積和（mod 3）を利用したDP」を組み合わせることで、全部分文字列を総当たりせずに線形時間で答えを得られます。同じ考え方はJavaやPythonなど他の言語にもそのまま応用可能です。問題を「8の倍数を数える」「3の倍数を取り除く」という2つのパートに分割すれば、非常にシンプルに解ける、文字列とDPを組み合わせた典型的なアルゴリズム問題だと言えます。