指定された文字列がC++の合計文字列であるかどうかを確認します

ここでは、文字列が合計文字列であるかどうかを確認する方法を説明します。右端の部分文字列がその前の2つの部分文字列の合計として記述できる場合、その文字列は合計文字列と呼ばれ、その前の部分文字列についても同じことが再帰的に当てはまります。 12243660のような文字列が12+24 =36のような合計文字列であり、36が文字列の12と24の後に存在し、再び24 + 36 =60であるとすると、これも文字列に存在します。

文字列Sは、この規則に従っている場合、合計文字列と呼ぶことができます-

𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔（𝑖、𝑥）+𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔（𝑥+ 1、𝑗）=𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔（𝑗+ 1、𝑙）

𝑎𝑛𝑑𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔（𝑥+ 1、𝑗）+𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔（𝑗+ 1、𝑙）=𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔（𝑙+ 1、𝑚）𝑎𝑛𝑑𝑠𝑜

例

#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";
}

出力

This is sum-string