C 프로그램에서 LCS의 공간 최적화 솔루션?

여기에서 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