9251: LCS

[minsoo0715]

9251: LCS

소스 코드

아이디어

• dp[i][j]를 다음과 같이 정의한다.

  str1의 i번째 까지의 부분 문자열과 str2의 i번째 까지의 부분 문자열의 LCS(길이)

• 두 문자열 ACAYKP, CAPCAK에 대해서 살펴보자

  • ACAY와 CAPCA
ACAY와 CAPCA의 LCS는 ACA이고,
    ACAYK와 CAPC의 LCS는 AC이다.
    이때 A, K로 다른 문자이므로, 두 경우 중 더 길이가 긴 것이 ACAYK CAPCA의 LCS라고 할 수 있다.

  • ACAYK와 CAPCAK
ACAY와 CAPCA의 LCS에 K를 추가하는 경우 이므로
    ACAY, CAPCA의 LCS에 K가 추가 된 문자열이 ACAYK와 CAPCAK의 LCS이다.

• 따라서 LCS의 길이는 다음과 같이 정리할 수 있다. ( string은 0-based, dp 배열은 1-based)

  • str1[i-1] == str2[j-1]일때
    dp[i][j] = dp[i-1][j-1] + 1
  • 아닐때
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

*	A	C	A	Y	K	P
C	0	0	0	0	0	0
A	0	0	0	0	0	0
P	0	0	0	0	0	0
C	0	0	0	0	0	0
A	0	0	0	0	0	0
K	0	0	0	0	0	0

i = 1 일 때 (string idx = 0)

*	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	0	0	0	0	0	0
P	0	0	0	0	0	0
C	0	0	0	0	0	0
A	0	0	0	0	0	0
K	0	0	0	0	0	0

반복

*	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	2	2	3	3	3	3
K	2	2	3	3	4	4

구현

for(int i = 1; i<=l1; ++i) {
    for(int j = 1; j<=l2; ++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]);
        }
    }
}