ধরুন আমাদের দুটি স্ট্রিং text1 এবং text2 আছে, আমাদের তাদের দীর্ঘতম সাধারণ অনুসারীর দৈর্ঘ্য খুঁজে বের করতে হবে। আমরা জানি যে একটি স্ট্রিং এর পরবর্তী স্ট্রিং হল একটি নতুন স্ট্রিং যা মূল স্ট্রিং থেকে কিছু অক্ষর মুছে ফেলা হয় এবং অবশিষ্ট অক্ষরের আপেক্ষিক ক্রম পরিবর্তন না করেই মুছে ফেলা হয়। (সুতরাং উদাহরণস্বরূপ "abe" হল "abcde" এর একটি অনুবর্তী কিন্তু "adc" নয়)। দুটি স্ট্রিং-এর একটি সাধারণ অনুবর্তন হল একটি অনুবর্তন যা উভয় স্ট্রিং-এর জন্য সাধারণ। সুতরাং কোন সাধারণ অনুবর্তন না থাকলে, 0 ফেরত দিন। যদি ইনপুটটি "abcde" এবং "ace" এর মত হয়, তাহলে ফলাফল 3 হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=s এর আকার, m :=x এর আকার
-
যদি n হয় 0, অথবা m 0 হয়, তাহলে 0
ফেরত দিন -
s :=খালি স্ট্রিং, s
এর সাথে সংযুক্ত -
x :=খালি স্ট্রিং, x
এর সাথে সংযুক্ত -
ret :=0
-
অর্ডারের একটি ম্যাট্রিক্স ডিপি সংজ্ঞায়িত করুন (n + 1) x (m + 1)
-
আমি 1 থেকে n
রেঞ্জের মধ্যে-
1 থেকে m
পরিসরে j এর জন্য-
dp[i, j] :=dp[i, j - 1] এবং dp[i – 1, j]
এর সর্বোচ্চ -
যদি s[i] =x[j], তাহলে
-
dp[i, j] :=dp[i, j] এর সর্বোচ্চ, 1 + dp[i – 1, j – 1]
-
-
-
-
dp[n, m]
ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestCommonSubsequence(string s, string x) {
int n = s.size();
int m = x.size();
if(!n || !m) return 0;
s = " " + s;
x = " " + x;
int ret = 0;
vector < vector <int> > dp(n + 1, vector <int>(m + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m ; j++){
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(s[i] == x[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.longestCommonSubsequence("abcde", "ace"));
} ইনপুট
"abcde" "ace"
আউটপুট
3
