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

দীর্ঘতম সাধারণ অনুক্রম হল এক ধরনের অনুক্রম যা প্রদত্ত অনুক্রম বা অ্যারে উভয়েই উপস্থিত থাকে৷

আমরা দেখতে পাচ্ছি যে অনেকগুলি উপ-সমস্যা রয়েছে, যেগুলি এই সমস্যাটি সমাধান করার জন্য বারবার গণনা করা হয়। ডায়নামিক প্রোগ্রামিংয়ের ওভারল্যাপিং সাবস্ট্রাকচার প্রপার্টি ব্যবহার করে, আমরা গণনামূলক প্রচেষ্টাকে অতিক্রম করতে পারি। একবার উপসমস্যাগুলির ফলাফল গণনা করা এবং টেবিলে সংরক্ষণ করা হলে, আমরা কেবল পূর্ববর্তী ফলাফলগুলি ব্যবহার করে পরবর্তী ফলাফলগুলি গণনা করতে পারি৷

ইনপুট এবং আউটপুট

Input:
Two strings with different letters or symbols.
string 1: AGGTAB
string 2: GXTXAYB
Output:
The length of the longest common subsequence. Here it is 4.
AGGTAB and GXTXAYB. The underlined letters are present in both strings and in correct sequence.

অ্যালগরিদম

longestComSubSeq(str1, str2)

ইনপুট - লংগেস্ট কমন সিক্যুয়েন্সের দৈর্ঘ্য খুঁজে পেতে দুটি স্ট্রিং।

আউটপুট − LCS এর দৈর্ঘ্য।

Begin
   m := length of str1
   n := length of str2
   define longSubSeq matrix of order (m+1) x (n+1)

   for i := 0 to m, do
      for j := 0 to n, do
         if i = 0 or j = 0, then
           longSubSeq[i,j] := 0
         else if str1[i-1] = str2[j-1], then
            longSubSeq[i,j] := longSubSeq[i-1,j-1] + 1
         else
            longSubSeq[i,j] := maximum of longSubSeq[i-1, j] and
            longSubSeq[i, j-1]
      done
   done

   longSubSeq[m, n]
End

উদাহরণ

#include<iostream>
using namespace std;

int max(int a, int b) {
   return (a > b)? a : b;
}

int longestComSs( string str1, string str2) {
   int m = str1.size();
   int n = str2.size();
   
   int longSubSeq[m+1][n+1];
   
   //longSubSeq[i,j] will hold the LCS of str1 (0 to i-1) and str2 (0 to j-1)
   for (int i=0; i<=m; i++) {
      for (int j=0; j<=n; j++) {
         if (i == 0 || j == 0)
            longSubSeq[i][j] = 0;
         else if (str1[i-1] == str2[j-1])
            longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1;
         else
            longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]);
      }
   }
   return longSubSeq[m][n];
}

int main() {
   string str1 = "AGGTAB";
   string str2 = "GXTXAYB";

   cout << "Length of Longest Common Subsequence is: " <<  longestComSs( str1, str2);
}

আউটপুট

Length of Longest Common Subsequence is: 4