मान लीजिए हमारे पास एक स्ट्रिंग 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