Kiểm tra xem một chuỗi đã cho có phải là chuỗi tổng trong C ++ hay không

Ở đây chúng ta sẽ xem cách kiểm tra xem một chuỗi có phải là chuỗi tổng hay không. Một chuỗi được cho là chuỗi tổng nếu chuỗi con ngoài cùng bên phải có thể được viết dưới dạng tổng của hai chuỗi con trước nó và điều này cũng đúng một cách đệ quy đối với chuỗi con trước nó. Giả sử một chuỗi như 12243660 là một chuỗi tổng, như 12 + 24 =36 và 36 có mặt sau 12 và 24 trong chuỗi, lại là 24 + 36 =60, đây cũng là chuỗi.

Một chuỗi S có thể được gọi là chuỗi tổng, nếu nó tuân theo quy tắc này -

𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 (𝑖, 𝑥) + 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 (𝑥 + 1, 𝑗) =𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 (𝑗 + 1, 𝑙)

𝑎𝑛𝑑 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 (𝑥 + 1, 𝑗) + 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 (𝑗 + 1, 𝑙) =𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 (𝑙 + 1, 𝑚) 𝑎𝑛𝑑 𝑠𝑜 𝑜𝑛

Ví dụ

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

Đầu ra

This is sum-string