가장 긴 공통 부분 수열을 위한 C++ 프로그램

하위 시퀀스는 요소 집합의 순서가 동일한 시퀀스입니다. "stuv" 시퀀스의 경우 하위 시퀀스는 "stu", "tuv", "suv" 등입니다.

길이가 n인 문자열의 경우 문자열에서 하위 시퀀스를 만드는 방법은 2n가지가 있습니다.

예시

" ABCDGH " 및 " AEDFHR " 문자열에 대한 가장 긴 공통 부분수열의 길이는 3입니다.

#include <iostream>
#include <string.h>
using namespace std;
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
   if (m == 0 || n == 0)
      return 0;
   if (X[m - 1] == Y[n - 1])
      return 1 + lcs(X, Y, m - 1, n - 1);
   else
      return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
int max(int a, int b){
   return (a > b) ? a : b;
}
int main(){
   char X[] = "AGGTAB";
   char Y[] = "GXTXAYB";
   int m = strlen(X);
   int n = strlen(Y);
   printf("Length of LCS is %d\n", lcs(X, Y, m, n));
   return 0;
}

출력

Length of LCS is 4