C++ এ দীর্ঘতম সাধারণ অনুবর্তন

ধরুন আমাদের দুটি স্ট্রিং text1 এবং text2 আছে, আমাদের তাদের দীর্ঘতম সাধারণ অনুসারীর দৈর্ঘ্য ফেরত দিতে হবে। একটি স্ট্রিং এর ubsequence হল একটি নতুন স্ট্রিং যা মূল স্ট্রিং থেকে উৎপন্ন হয় যার সাথে কিছু অক্ষর মুছে ফেলা হয় অবশিষ্ট অক্ষরের আপেক্ষিক ক্রম পরিবর্তন না করে। (সুতরাং উদাহরণস্বরূপ "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