가장 긴 공통 부분 수열

가장 긴 공통 하위 시퀀스는 지정된 시퀀스 또는 배열 모두에 존재하는 하위 시퀀스 유형입니다.

이 문제를 해결하기 위해 계속해서 계산되는 많은 하위 문제가 있음을 알 수 있습니다. 동적 프로그래밍의 중첩 하위 구조 속성을 사용하여 계산 노력을 극복할 수 있습니다. 하위 문제의 결과가 계산되어 테이블에 저장되면 이전 결과를 사용하여 다음 결과를 간단히 계산할 수 있습니다.

입력 및 출력

Input:
Two strings with different letters or symbols.
string 1: AGGTAB
string 2: GXTXAYB
Output:
The length of the longest common subsequence. Here it is 4.
AGGTAB and GXTXAYB. The underlined letters are present in both strings and in correct sequence.

알고리즘

longestComSubSeq(str1, str2)

입력 - Longest Common Subsequence의 길이를 찾는 두 개의 문자열.

출력 - LCS의 길이.

Begin
   m := length of str1
   n := length of str2
   define longSubSeq matrix of order (m+1) x (n+1)

   for i := 0 to m, do
      for j := 0 to n, do
         if i = 0 or j = 0, then
           longSubSeq[i,j] := 0
         else if str1[i-1] = str2[j-1], then
            longSubSeq[i,j] := longSubSeq[i-1,j-1] + 1
         else
            longSubSeq[i,j] := maximum of longSubSeq[i-1, j] and
            longSubSeq[i, j-1]
      done
   done

   longSubSeq[m, n]
End

예시

#include<iostream>
using namespace std;

int max(int a, int b) {
   return (a > b)? a : b;
}

int longestComSs( string str1, string str2) {
   int m = str1.size();
   int n = str2.size();
   
   int longSubSeq[m+1][n+1];
   
   //longSubSeq[i,j] will hold the LCS of str1 (0 to i-1) and str2 (0 to j-1)
   for (int i=0; i<=m; i++) {
      for (int j=0; j<=n; j++) {
         if (i == 0 || j == 0)
            longSubSeq[i][j] = 0;
         else if (str1[i-1] == str2[j-1])
            longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1;
         else
            longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]);
      }
   }
   return longSubSeq[m][n];
}

int main() {
   string str1 = "AGGTAB";
   string str2 = "GXTXAYB";

   cout << "Length of Longest Common Subsequence is: " <<  longestComSs( str1, str2);
}

출력

Length of Longest Common Subsequence is: 4