सी ++ में सबसे लंबे समय तक दोहराए जाने वाले सबस्ट्रिंग

मान लीजिए कि हमारे पास एक स्ट्रिंग एस है, हमें सबसे लंबे समय तक दोहराए जाने वाले सबस्ट्रिंग की लंबाई का पता लगाना है। यदि कोई दोहराई जाने वाली सबस्ट्रिंग मौजूद नहीं है तो हम 0 वापस कर देंगे। तो अगर स्ट्रिंग "अब्बाबा" की तरह है, तो आउटपुट 2 होगा। सबसे लंबे समय तक दोहराए जाने वाले सबस्ट्रिंग "ab" या "ba" है।

इस तरह से बनने वाले सभी शब्दों को शब्दावली क्रम में लौटाएं।

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

n :=S का आकार
सेट एस:=एक रिक्त स्थान जो एस के साथ जुड़ा हुआ है
सेट रिट :=0
आकार का एक मैट्रिक्स डीपी बनाएं (एन + 1) एक्स (एन + 1)
मैं के लिए 1 से n की सीमा में
- i + 1 से n की श्रेणी में j के लिए
  - अगर एस [i] =एस [जे]
    - dp[i, j] :=अधिकतम dp[i, j] और 1 + dp[i – 1, j-1]
    - ret :=अधिकतम रिट और dp[i, j]
वापसी रिट

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestRepeatingSubstring(string S) {
      int n = S.size();
      S = " " + S;
      int ret = 0;
      vector < vector <int> > dp(n + 1, vector <int> (n + 1));
      for(int i = 1; i <= n; i++){
         for(int j = i + 1; j <= n; j++){
            if(S[i] == S[j]){
               dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
               ret = max(ret, dp[i][j]);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.longestRepeatingSubstring("abbaba"));
}

इनपुट

"abbaba"