ধরুন আমাদের একটি স্ট্রিং S আছে, আমাদেরকে দীর্ঘতম পুনরাবৃত্তিকারী সাবস্ট্রিং(গুলি) এর দৈর্ঘ্য খুঁজে বের করতে হবে। কোনো পুনরাবৃত্তি সাবস্ট্রিং উপস্থিত না থাকলে আমরা 0 ফেরত দেব। তাই যদি স্ট্রিংটি "abbaba" এর মত হয়, তাহলে আউটপুট হবে 2। যেহেতু দীর্ঘতম পুনরাবৃত্তি সাবস্ট্রিং হল "ab" বা "ba"।
আভিধানিক ক্রমে, এই পদ্ধতিতে গঠিত হতে পারে এমন সমস্ত শব্দ ফেরত দিন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=S
এর আকার -
S:=S
এর সাথে সংযুক্ত একটি ফাঁকা স্থান সেট করুন -
সেট ret :=0
-
আকারের একটি ম্যাট্রিক্স ডিপি তৈরি করুন (n + 1) x (n + 1)
-
আমি 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]
-এর সর্বোচ্চ
-
-
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
