यहां हम देखेंगे कि कोई स्ट्रिंग सम-स्ट्रिंग (sum-string) है या नहीं, इसकी जांच कैसे करें। एक स्ट्रिंग को सम-स्ट्रिंग कहा जाता है यदि इसका सबसे दायां सबस्ट्रिंग, उससे पहले के दो सबस्ट्रिंग के योग के रूप में लिखा जा सकता है, और यही नियम उससे पहले के सबस्ट्रिंग के लिए पुनरावर्ती रूप से सत्य होता है। मान लीजिए 12243660 जैसी स्ट्रिंग एक सम-स्ट्रिंग है, क्योंकि 12 + 24 = 36, और 36 स्ट्रिंग में 12 और 24 के बाद मौजूद है, फिर 24 + 36 = 60, यह भी स्ट्रिंग में मौजूद है।
एक स्ट्रिंग 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
