[Algorithm Tech]공통 부분 문자열과 최장 공통 부분 수열

* 개념 이해

공통 부분 문자열과 최장 공통 부분 수열은 비슷한점이 많다.

공통 부분 문자열(Longest Common Substring)은 중간에 끊어지는 값이 이어지는 부분 배열중에서 문자열을 찾는 방식이고,

최장 공통 부분 수열(Longest Common Subsequence)은 문자열이 연속되지 않아도 선택이 가능하다.

위와 같은 예시가 있을 때,

공통 부분 문자열은 BCD, 최장 공통 부분 수열은 BCDEF 가 될 것이다.

* 공통 부분 문자열

문자열 A와 B가 있을 때,

dp[i][j] = A문자열은 i번째, B문자열은 j번째 글자까지 비교했을 때 가장 긴 공통 부분 문자열의 길이

예를 들어 ABCD와 DBCA를 비교한다고 생각해보자.

	A	B	C	D
D	0	0	0	1
B	0	1	0	0
C	0	0	2	0
A	1	0	0	0

DBC와 ABC를 비교했을 때 공통 부분 문자열은 BC가 있으므로 답은 2가 될 것이다.

이를 코드로 구현하면 다음과 같다.

char[] ch1 = br.readLine().toCharArray();
char[] ch2 = br.readLine().toCharArray();
int[][] dp = new int[ch1.length + 1][ch2.length + 1];
 
for (int i = 0; i < ch1.length; i++) {
    for (int j = 0; j < ch2.length; j++) {
        if (ch1[i] == ch2[j]) {        //비교하는 글자가 같으면 이전 문자열 길이 + 1
            dp[i + 1][j + 1] = dp[i][j] + 1;
        } 
    }
}

* 최장 공통 부분 수열(Longest Common Subsequence) 

문자열 A와 B가 있을 때, 

dp[i][j] = A문자열은 i번째, B문자열은 j번째 글자까지 비교했을 때의 최장 공통 부분 수열의 길이

예를 들어, ABCD와 BACD를 비교한다고 생각해보자.

	A	B	C	D
B	0	1	1	1
A	1	1	1	1
C	1	1	2	2
D	1	1	2	3

(3,3) 값을 보면 2라는 값이 나오는데, 이는 BAC와 ABC를 비교한 값이다. 

dp에는 이전 까지 저장된 최장 공통 부분 수열의 길이를 저장하고 A문자열 i번째와 B문자열 j번째가 같으면 +1을 해주면 된다.

A문자열 i번째와 B문자열 j번째가 같지 않더라도 이전까지 구한 값이 최장 공통 부분 수열이기 때문에 (i-1,j)와 (i,j-1) 중에서 최대값을 저장하면 된다.

만약, LCS의 문자열을 구해야 한다면, (i,j)부터 회색으로 색칠된 부분의 문자열만 추가하는 방식으로 진행하면 될 것이다.

이를 코드로 구현하면 다음과 같다.

char[] ch1 = br.readLine().toCharArray();
char[] ch2 = br.readLine().toCharArray();
int[][] dp = new int[ch1.length + 1][ch2.length + 1];
 
for (int i = 0; i < ch1.length; i++) {
    for (int j = 0; j < ch2.length; j++) {
        if (ch1[i] == ch2[j]) {        //비교하는 글자가 같으면 이전 문자열 길이 + 1
            dp[i + 1][j + 1] = dp[i][j] + 1;
        } else {                    //비교하는 글자가 다르면 이전 문자열중 max값 저장
            dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
        }
    }
}