A Space Optimized Solution ของ LCS ในโปรแกรม C?

ในที่นี้ เราจะเห็นแนวทางหนึ่งที่ปรับพื้นที่ให้เหมาะสมสำหรับปัญหา 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