C++ में बार-बार सबस्ट्रिंग पैटर्न

मान लीजिए कि हमारे पास एक गैर-रिक्त स्ट्रिंग है। हमें यह जांचना होगा कि क्या इसका एक सबस्ट्रिंग लेकर और सबस्ट्रिंग के कई बार जोड़कर इसका निर्माण किया जा सकता है। स्ट्रिंग में केवल लोअरकेस अंग्रेजी अक्षर होते हैं और इसकी लंबाई 10000 से अधिक नहीं होगी। इसलिए यदि इनपुट "अबाबाबा" जैसा है, तो उत्तर सही होगा, क्योंकि यह "एबा" का उपयोग करके बनाया गया है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• हम गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।
• आकार n के एक सरणी DP को परिभाषित करें। n स्ट्रिंग का आकार है
• i :=1 और j :=0
• जबकि मैं
• अगर str[i] ==str[j], तो DP[i] :=j + 1, i और j को 1 से बढ़ाएं
• अन्यथा
  • अगर j> 0, तो j :=DP[j – 1]
  • अन्य dp[i] :=0, और i को 1 से बढ़ाएँ

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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