मान लीजिए हमारे पास एक गैर-खाली स्ट्रिंग है। हमें जांचना है कि क्या इसे इसके एक उपस्ट्रिंग को लेकर और उपस्ट्रिंग को कई बार जोड़कर बनाया जा सकता है। स्ट्रिंग में केवल लोअरकेस अंग्रेजी अक्षर होते हैं और इसकी लंबाई 10000 से अधिक नहीं होगी। इसलिए यदि इनपुट "abaabaaba" जैसा है, तो उत्तर true होगा, क्योंकि यह "aba" का उपयोग करके बनाया गया है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।
- आकार n की एक सरणी DP परिभाषित करें। n स्ट्रिंग का आकार है
- i := 1 और j := 0
- जब तक i < n
- यदि str[i] == str[j], तो DP[i] := j + 1, i और j को 1 से बढ़ाएं
- अन्यथा
- यदि j > 0, तो j := DP[j - 1]
- अन्यथा dp[i] := 0, और i को 1 से बढ़ाएं
- यदि DP[n - 1] 0 नहीं है और n % (n - DP[n - 1]) == 0
- true वापस करें
- अन्यथा false वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; class Solution { public: void printVector(vector <int> v){ for(int i = 0; i < v.size(); i++)cout << v[i] << " "; cout << endl; } bool repeatedSubstringPattern(string s) { int n = s.size(); vector <int> dp(n); int i = 1; int j = 0; while(i < n){ if(s[i] == s[j]){ dp[i] = j+1; i++; j++; } else { if(j > 0){ j = dp[j-1]; } else { dp[i] = 0; i++; } } } return dp[n - 1] && n % (n - dp[n-1]) == 0; } }; main(){ Solution ob; string res = (ob.repeatedSubstringPattern("abaabaaba"))? "true" : "fasle"; cout << res; } इनपुट
"abaabaaba"
आउटपुट
true
