এখানে আমরা দেখব কিভাবে একটি স্ট্রিং সম-স্ট্রিং কিনা তা পরীক্ষা করা যায়। একটি স্ট্রিংকে যোগ-স্ট্রিং বলা হয় যদি ডানদিকের সাবস্ট্রিংটিকে তার আগে দুটি সাবস্ট্রিংয়ের যোগফল হিসাবে লেখা যায় এবং এটি তার আগে সাবস্ট্রিংয়ের জন্য পুনরাবৃত্তিমূলকভাবে সত্য। ধরুন 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
