[알고리즘] LCS (최장 공통 수열)

문자열은 최대길이 1000.

dp배열은 최대길이 1000 + 1.

 

dp배열을 1인덱스 부터 채워나가고, 그렇기에 반복문에서 문자열의 값을 사용할 때엔 인덱스를 - 1 해준다.

 

같을 경우 : dp[i][j] = dp[i - 1][j - 1] + 1

다를 경우 : dp[i][j] = MAX(dp[i][j - 1], dp[i - 1][j])

#include <stdio.h>
#include <string.h>
#define MAX(a,b) ((a>=b))?a:b;

char str1[1000], str2[1000];
int dp[1001][1001];
int len1, len2;

int main() {
    scanf("%s", str1);
    scanf("%s", str2);
    
    len1 = strlen(str1);
    len2 = strlen(str2);
    
    for(int i = 1; i <= len1; i++) {
        for(int j = 1; j <= len2; j++) {
            if(str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = MAX(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    
    printf("%d", dp[len1][len2]);
}

 

참고

hevton.tistory.com/350