C++で指定された文字列がサムストリング（合計文字列）かどうかを判定する方法

この記事では、与えられた文字列が「サムストリング（sum-string：合計文字列）」であるかどうかを判定する方法を、C++のコード例とともにわかりやすく解説します。

サムストリングとは？

サムストリングとは、右端の部分文字列が、その直前にある2つの部分文字列の和として表せ、さらにその関係が文字列の先頭に向かって再帰的に成り立つ文字列のことです。

例として「12243660」という文字列を見てみましょう。

• 12 + 24 = 36 → 「36」は「12」「24」の直後に存在する
• 24 + 36 = 60 → 「60」は「24」「36」の直後に存在する

このように条件が連鎖的に満たされるため、「12243660」はサムストリングであると言えます。

数学的な定義

文字列 S がサムストリングであるためには、次の規則を満たす必要があります。

substring(i, x) + substring(x+1, j) = substring(j+1, l)

substring(x+1, j) + substring(j+1, l) = substring(l+1, m)

以降も同様に、隣り合う2つの部分文字列の和が、その直後の部分文字列と一致し続けることが求められます。

C++での実装

以下のコードでは、大きな数値にも対応できるよう、数値を文字列のまま足し算する関数 get_string_sum() を用意し、それを利用して条件を再帰的に検証しています。

#include <bits/stdc++.h>
using namespace std;
string get_string_sum(string str1, string str2) {
    if (str1.size() < str2.size())
        swap(str1, str2);
    int len1 = str1.size();
    int len2 = str2.size();
    string ans = "";
    int carry = 0;
    for (int i = 0; i < len2; i++) {
        int ds = ((str1[len1 - 1 - i] - '0') + (str2[len2 - 1 - i] - '0') + carry) % 10;
        carry = ((str1[len1 - 1 - i] - '0') + (str2[len2 - 1 - i] - '0') + carry) / 10;
        ans = char(ds + '0') + ans;
    }
    for (int i = len2; i < len1; i++) {
        int ds = (str1[len1 - 1 - i] - '0' + carry) % 10;
        carry = (str1[len1 - 1 - i] - '0' + carry) / 10;
        ans = char(ds + '0') + ans;
    }
    if (carry)
        ans = char(carry + '0') + ans;
    return ans;
}
bool sumStrCheckHelper(string str, int beg, int len1, int len2) {
    string sub1 = str.substr(beg, len1);
    string sub2 = str.substr(beg + len1, len2);
    string sum = get_string_sum(sub1, sub2);
    int sum_len = sum.size();
    if (sum_len > str.size() - len1 - len2 - beg)
        return false;
    if (sum == str.substr(beg + len1 + len2, sum_len)) {
        if (beg + len1 + len2 + sum_len == str.size())
            return true;
        return sumStrCheckHelper(str, beg + len1, len2, sum_len);
    }
    return false;
}
bool isSumStr(string str) {
    int n = str.size();
    for (int i = 1; i < n; i++)
        for (int j = 1; i + j < n; j++)
            if (sumStrCheckHelper(str, 0, i, j))
                return true;
    return false;
}
int main() {
    if(isSumStr("1212243660"))
        cout << "This is sum-string";
    else
        cout << "This is not sum-string";
}

コードのポイント

• get_string_sum()： 桁数の異なる2つの数値文字列の和を、繰り上がり処理も含めて正確に計算します。これにより、int型の範囲を超える大きな数でも扱えます。
• sumStrCheckHelper()： 開始位置と最初の2つの部分文字列の長さを受け取り、その和が次の部分文字列と一致するかを再帰的に確認します。文字列の末尾まで条件が成立すれば true を返します。
• isSumStr()： 最初の2つの部分文字列の長さの組み合わせをすべて試し、1つでも成立するパターンがあれば true を返します。

実行結果

This is sum-string