এখানে আমরা দেখব কিভাবে একটি স্ট্রিং সম-স্ট্রিং (sum-string) কিনা তা নির্ধারণ করা যায়। একটি স্ট্রিংকে সম-স্ট্রিং বলা হয় যদি এর ডান পাশের সাবস্ট্রিংটি তার আগের দুটি সাবস্ট্রিংয়ের যোগফল হিসেবে লেখা যায়, এবং এই নিয়মটি পূর্ববর্তী সাবস্ট্রিংয়ের জন্যও রিকার্সিভভাবে সত্য থাকে। উদাহরণস্বরূপ, ১২২৪৩৬৬০ একটি সম-স্ট্রিং, কারণ ১২ + ২৪ = ৩৬, এবং ৩৬ স্ট্রিংয়ে ১২ ও ২৪-এর পরে অবস্থিত; আবার ২৪ + ৩৬ = ৬০, যা স্ট্রিংয়ে আছে।
একটি স্ট্রিং S সম-স্ট্রিং হবে যদি এটি নিচের নিয়ম মেনে চলে:
substring(i, x) + substring(x+1, j) = substring(j+1, l)
এবং substring(x+1, j) + substring(j+1, l) = substring(l+1, m) ইত্যাদি।
উদাহরণ
#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
