เราจะมาดูวิธีการตรวจสอบว่า string เป็น sum-string หรือไม่ สตริงถูกเรียกว่า sum-string ถ้าสตริงย่อยด้านขวาสุดสามารถเขียนเป็นผลรวมของสองสตริงย่อยก่อนหน้านั้น และสตริงย่อยก่อนหน้านั้นจะเป็นแบบเรียกซ้ำ สมมติว่าสตริงเช่น 12243660 เป็นสตริงผลรวม เช่น 12 + 24 =36 และ 36 อยู่หลัง 12 และ 24 ในสตริง และอีก 24 + 36 =60 มีอยู่ในสตริงด้วย
สตริง S สามารถเรียกว่า sum-string ได้ หากเป็นไปตามกฎนี้ -
𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔(𝑖,𝑥)+𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔(𝑥+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
