সি প্রোগ্রামে এলসিএসের একটি স্পেস অপ্টিমাইজড সমাধান?

এখানে আমরা LCS সমস্যার জন্য একটি স্পেস অপ্টিমাইজড পদ্ধতি দেখতে পাব। LCS হল সবচেয়ে দীর্ঘতম সাধারণ অনুসৃতি। যদি দুটি স্ট্রিং হয় “BHHUBC” এবং “HYUYBZC”, তাহলে তার পরের দৈর্ঘ্য হবে 4। একটি ডায়নামিক প্রোগ্রামিং অ্যাপ্রোচ ইতিমধ্যেই তাদের, কিন্তু ডাইনামিক প্রোগ্রামিং অ্যাপ্রোচ ব্যবহার করলে এটি আরও জায়গা নেবে। আমাদের m x n এর সারণী দরকার, যেখানে m হল প্রথম স্ট্রিং-এর অক্ষরের সংখ্যা এবং n হল দ্বিতীয় স্ট্রিং-এর অক্ষরের সংখ্যা।

এখানে আমরা O(n) পরিমাণ অক্জিলিয়ারী স্পেস ব্যবহার করে কিভাবে এই অ্যালগরিদম বাস্তবায়ন করতে হয় তা দেখব। যদি আমরা পুরানো পদ্ধতিটি পর্যবেক্ষণ করি যা আমরা প্রতিটি পুনরাবৃত্তিতে দেখতে পারি, আমাদের পূর্ববর্তী সারি থেকে ডেটা প্রয়োজন। সমস্ত ডেটা প্রয়োজন হয় না। সুতরাং আমরা যদি 2n আকারের একটি টেবিল তৈরি করি, তাহলে এটি ঠিক হবে। আসুন ধারণা পেতে অ্যালগরিদম দেখি।

অ্যালগরিদম

lcs_problem(X, Y) -

begin
   m := length of X
   n := length of Y
   define table of size L[2, n+1]
   index is to point 0th or 1st row of the table L.
   for i in range 1 to m, do
      index := index AND 1
      for j in range 0 to n, do
         if i = 0 or j = 0, then
            L[index, j] := 0
         else if X[i - 1] = Y[j - 1], then
            L[index, j] := L[1 – index, j - 1] + 1
         else
            L[index, j] := max of L[1 – index, j] and L[index, j-1]
         end if
      done
   done
   return L[index, n]
end

উদাহরণ

#include <iostream>
using namespace std;
int lcsOptimized(string &X, string &Y) {
   int m = X.length(), n = Y.length();
   int L[2][n + 1];
   bool index;
   for (int i = 0; i <= m; i++) {
      index = i & 1;
      for (int j = 0; j <= n; j++) {
         if (i == 0 || j == 0)
            L[index][j] = 0;
         else if (X[i-1] == Y[j-1])
            L[index][j] = L[1 - index][j - 1] + 1;
         else
            L[index][j] = max(L[1 - index][j], L[index][j - 1]);
      }
   }
   return L[index][n];
}
int main() {
   string X = "BHHUBC";
   string Y = "HYUYBZC";
   cout << "Length of LCS is :" << lcsOptimized(X, Y);
}

আউটপুট

Length of LCS is :4