সর্বোচ্চ সাধারণ সাবসিকোয়েন্স (LCS)

সর্বোচ্চ সাধারণ সাবসিকোয়েন্স হল এমন একটি সাবসিকোয়েন্স যা প্রদত্ত দুটি সিকোয়েন্স বা অ্যারেতে উপস্থিত থাকে।

এই সমস্যায় অনেক উপসমস্যা থাকে যা বারবার গণনা করতে হয়। ডাইনামিক প্রোগ্রামিং-এর ওভারল্যাপিং সাবস্ট্রাকচার প্রোপার্টি ব্যবহার করে এই কম্পিউটেশনাল ঝামেলা দূর করা যায়। একবার উপসমস্যার ফলাফল টেবিলে সংরক্ষণ করলে পরবর্তী ফলাফল সহজে পাওয়া যায়।

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

ইনপুট: ভিন্ন অক্ষর বা চিহ্ন সহ দুটি স্ট্রিং।
string 1: AGGTAB
string 2: GXTXAYB

আউটপুট: সর্বোচ্চ সাধারণ সাবসিকোয়েন্সের দৈর্ঘ্য। এখানে এটি ৪।
AGGTAB এবং GXTXAYB। আন্ডারলাইন করা অক্ষরদুই স্ট্রিংয়েও সঠিক ক্রমে উপস্থিত।

অ্যালগরিদম

longestComSubSeq(str1, str2)

ইনপুট: LCS দৈর্ঘ্য খুঁজে বের করার জন্য দুটি স্ট্রিং।
আউটপুট: LCS-এর দৈর্ঘ্য।

শুরু
  m := str1-এর দৈর্ঘ্য
  n := str2-এর দৈর্ঘ্য
  (m+1) x (n+1) ক্রমের longSubSeq ম্যাট্রিক্স সংজ্ঞায়িত করুন
  i := 0 থেকে m পর্যন্ত, করুন
    j := 0 থেকে n পর্যন্ত, করুন
      যদি i = 0 বা j = 0 হয়, তবে
        longSubSeq[i,j] := 0
      অন্যথায় যদি str1[i-1] = str2[j-1] হয়, তবে
        longSubSeq[i,j] := longSubSeq[i-1,j-1] + 1
      অন্যথায়
        longSubSeq[i,j] := longSubSeq[i-1, j] এবং longSubSeq[i, j-1] এর মধ্যে সর্বোচ্চ
    শেষ
  শেষ
  longSubSeq[m, n] ফেরত দিন
শেষ

উদাহরণ (C++)

#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];

  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