এখানে LCS সমস্যার জন্য একটি স্পেস অপ্টিমাইজড পদ্ধতি দেখব। LCS হলো লংগেস্ট কমন সাবসিকোয়েন্স। যদি দুটি স্ট্রিং হয় “BHHUBC” এবং “HYUYBZC”, তবে সাবসিকোয়েন্সের দৈর্ঘ্য ৪। একটি ডাইনামিক প্রোগ্রামিং পদ্ধতি ইতিমধ্যে আছে, কিন্তু সেটি বেশি স্পেস নেয়। সেটিতে m x n আকারের টেবিল লাগে, যেখানে m হলো প্রথম স্ট্রিংয়ের ক্যারেক্টার সংখ্যা এবং n দ্বিতীয় স্ট্রিংয়ের।
এখানে আমরা দেখব কীভাবে O(n) অক্সিলিয়ারি স্পেসে এই অ্যালগরিদম বাস্তবায়ন করা যায়। পুরনো পদ্ধতিতে প্রতিটি ইটারেশনে আগের রোয়ের ডেটা লাগে। সকল ডেটা লাগে না। তাই যদি ২n আকারের টেবিল বানাই, তবে চলবে। অ্যালগরিদম দেখুন।
অ্যালগরিদম
lcs_problem(X, Y) −
শুরু m := X-এর দৈর্ঘ্য n := Y-এর দৈর্ঘ্য L[2, n+1] আকারের টেবিল ডিক্লেয়ার করুন index হচ্ছে টেবিলের ০ নম্বর বা ১ নম্বর রো নির্দেশক। 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] শেষ
উদাহরণ
#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
