<백준 알고리즘> 9251번: LCS

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1

ACAYKP CAPCAK

예제 출력 1

4

---

Solution

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int max2(int x,int y)
{
   return x>y?x:y;
}

int max3(int x,int y,int z)
{
   return x>=y&&x>=z?x:y>=x&&y>=z?y:z;
}

int main(void)
{
   char A[1001]={'\0', }, B[1001]={'\0', };
   int **LCS=NULL, a, b;

   scanf("%s%s", A, B);
   a=strlen(A);
   b=strlen(B);

   LCS=(int **)malloc((a+1)*sizeof(int *));
   for(int i=0;i<=a;i++)
      LCS[i]=(int *)calloc(b+1,sizeof(int));

   for(int i=1;i<=a;i++)
      for(int j=1;j<=b;j++)
         if(A[i-1]!=B[j-1])
            LCS[i][j]=max2(LCS[i-1][j],LCS[i][j-1]);
         else
            LCS[i][j]=max3(LCS[i-1][j],LCS[i][j-1],LCS[i-1][j-1]+1);

   printf("%d\n", LCS[a][b]);
   for(int i=0;i<=a;i++)
      free(LCS[i]);
   free(LCS);
   return 0;
}