Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में लॉन्गेस्ट रिपीटिंग सबस्ट्रिंग


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

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

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

  • n := S का आकार

  • S := एक खाली स्थान के साथ S संयोजित करें

  • ret := 0 सेट करें

  • आकार (n + 1) x (n + 1) का एक मैट्रिक्स dp बनाएं

  • i को 1 से n तक रेंज में लिए:

    • j को i + 1 से n तक रेंज में लिए:

      • यदि S[i] = S[j]

        • dp[i, j] := dp[i, j] का अधिकतम और 1 + dp[i - 1, j - 1]

        • ret := ret का अधिकतम और dp[i, j]

  • ret लौटाएं

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

उदाहरण

#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"

आउटपुट

2

  1. - C++ प्रोग्राम: सबसे लंबा सामान्य उपस्ट्रिंग (Longest Common Substring) प्रिंट करना

    इस ट्यूटोरियल में, हम सबसे लंबे सामान्य उपस्ट्रिंग (longest common substring) को प्रिंट करने के प्रोग्राम पर चर्चा करेंगे। इसके लिए हमें दो स्ट्रिंग्स A और B दी जाएंगी। हमें इनपुट स्ट्रिंग्स A और B दोनों के लिए सामान्य सबसे लंबा उपस्ट्रिंग प्रिंट करना होगा। उदाहरण के लिए, यदि हमें HelloWorld और wo

  1. - C++ में सबस्ट्रिंग

    सबस्ट्रिंग एक स्ट्रिंग का हिस्सा है। C++ में सबस्ट्रिंग प्राप्त करने के लिए एक फ़ंक्शन substr() है। इस फ़ंक्शन में दो पैरामीटर्स होते हैं: pos और len। pos पैरामीटर सबस्ट्रिंग की शुरुआती पोजीशन निर्दिष्ट करता है और len सबस्ट्रिंग में कैरेक्टर्स की संख्या दर्शाता है। उदाहरण #include <iostream>

  1. - पायथन में बिना दोहराव वाले वर्णों का सबसे लंबा सबस्ट्रिंग

    मान लीजिए हमारे पास एक स्ट्रिंग है। हमें बिना वर्णों को दोहराए सबसे लंबा सबस्ट्रिंग ढूंढना है। इसलिए यदि स्ट्रिंग ABCABCBB जैसी है, तो परिणाम 3 होगा, क्योंकि लंबाई 3 का एक सबस्ट्रिंग है जो दोहरा रहा है। वह है ABC। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे: i := 0, j := 0 सेट करें, जानकारी स्