ตรวจสอบว่า String เป็น Sum-String หรือไม่ใน C++

ในบทความนี้เราจะมาดูวิธีการตรวจสอบว่า String ที่กำหนดเป็น Sum-String หรือไม่ String ถือว่าเป็น Sum-String หาก substring สุดท้ายทางขวาสามารถเขียนในรูปของผลรวมของ substring สองตัวก่อนหน้าได้ และเงื่อนไขเดียวกันนี้ยังคงเป็นจริงอย่างต่อเนื่องสำหรับ substring ก่อนหน้า ตัวอย่างเช่น String "12243660" เป็น Sum-String เพราะ 12 + 24 = 36 และ 36 อยู่หลัง 12 และ 24 ใน String อีกครั้ง 24 + 36 = 60 ซึ่งก็อยู่ใน String เช่นกัน

String S จะเรียกว่า Sum-String ได้ หากปฏิบัติตามกฎนี้:

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

และ substring(x+1, j) + substring(j+1, l) = substring(l+1, m) และทำต่อไป

ตัวอย่างโค้ด C++

#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