C 프로그램의 LCS를 위한 공간 최적화 솔루션?

여기서 LCS 문제에 대한 공간 최적화 방법을 살펴보겠습니다. LCS는 가장 긴 공통 부분 수열입니다. 두 문자열이 "BHHUBC" 및 "HYUYBZC"인 경우 하위 시퀀스의 길이는 4입니다. 동적 프로그래밍 방법은 이미 그 중 하나이지만 동적 프로그래밍 방법을 사용하면 더 많은 공간을 차지하게 됩니다. m x n 순서의 테이블이 필요합니다. 여기서 m은 첫 번째 문자열의 문자 수이고 n은 두 번째 문자열의 문자 수입니다.

O(n)개의 보조 공간을 활용하는 방법을 알아 보겠습니다. 이전 접근 방식을 살펴보면 각 반복마다 이전 행의 데이터가 필요하다는 것을 알 수 있습니다. 모든 데이터가 필요한 것은 아닙니다. 따라서 크기가 2n인 테이블을 만들면 문제가 되지 않습니다. 이 아이디어를 이해하기 위해 알고리즘을 살펴보겠습니다.

Algorithm

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

Example

#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);
}

Output

Length of LCS is :4

위 내용은 C 프로그램의 LCS를 위한 공간 최적화 솔루션?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!