LCS (Longest Common Subsequence)란 최장 공통 부분 문자열이다. Subsequence의 뜻은 부분 수열 이라는 의미로 문자열이 연속적이지 않아도 된다는 의미이다.
즉, 두 문자열 a, b를 비교할 때 공통 부분 수열 중 길이가 가장 긴 부분 수열을 의미한다.
예를들어, 문자열 "acaykp"와 "capcak"의 LCS를 구해보자.
dp[3][3]이라면 "acaykp"에서는 3번째 문자열인 a까지만(3개), "capcak"에서는 p까지만 (3개)까지 문자열 비교를 한다.
이 경우 a!=p 서로 다른 문자이므로 p[3][2] = 2, dp[2][3] = 1 중에서 더 큰 값인 2를 dp[3][3]에 넣어주면 된다.
만약 서로 같은 문자인 경우에는 dp[2][2]+1의 값을 넣어주면 된다.
점화식을 통해 다시 설명해보자.
if (i == 0 or j == 0)일 경우 겹치는 문자가 존재하지 않기 때문에 0이다.
i, j > 0이면서 x(i)=y(j)로 문자가 겹친다면, c[i][j] = c[i - 1][j - 1]+1 이다.
i, j > 0 이면서 x(i)!=y(j)로 문자가 겹치지 않는다면, c[i][j] = max(c[i - 1][j], c[i][j-1])이다.
따라서 구하고자 하는 LCS의 길이는 가장 오른쪽 아래의 dp[6][6] = 4이다.
이 점화식을 코드로 나타내면 다음과 같다.
for (int i = 1; i <= a.length; i++) {
for (int j = 1; j <= b.length; j++) {
if(a[i] == b.[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}만약, LCS가 무엇인지 알고 싶다면 어떻게 해야 할까?
역추적(Back Tracking)을 이용해서 구하면 된다.
위의 주황색으로 표시된 내용을 보면, dp[6][6]을 보았을 때 어떤 경로를 통해서 왔는지 역추적으로 출발 지점을 따라가면 된다. a[i]==b[j]라면 dp[i-1][j-1]의 위치로 이동하면 되고, 그렇지 않다면 dp[i-1][j] dp[i][j-1]중에 큰 값으로 이동하면 된다.
역추적을 코드로 나타내면 다음과 같다.
static String backTracking(String a, String b, int i, int j) {
if(i==0 || j==0) return "";
else if (a.charAt(i) == b.charAt(j)) return backTracking(a, b, i-1, j-1) + a.charAt(i);
if(dp[i][j-1] >= dp[i-1][j]) return backTracking(a, b, i, j-1);
else return backTracking(a, b, i-1, j);
}- 활용 문제
- SWEA - 최장 공통 부분 수열
