자바 최장 부분 공통 서열(Longest Common Subsequence) - DP 이용

1. 개요

최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.)

컴퓨터 과학에서 고전으로 통하는 문제이며, diff 유틸리티의 근간이 되며, 생물정보학에서도 많이 응용되고 있다. 이 문제는 연속되어 있는 공통 문자열을 찾는 최장 공통 부분문자열(longest common substring) 문제와 혼동해서는 안 된다.

2. 코드 예제

public class LongestCommonSubsequence {
	public static void main(String[] args) {
		String a = "abcdabcdabcd";
		String b = "bcda";

		LongestCommonSubsequence lcs = new LongestCommonSubsequence();
		System.out.println(lcs.solution(a, b));
	}

	private int solution(String a, String b) {
		if (a.length() == 0 || b.length() == 0) {
			return 0;
		} else if (a.charAt(0) == b.charAt(0)) {
			return 1 + solution(a.substring(1, a.length()), b.substring(1, b.length()));
		} else {
			return max(
					solution(a.substring(1, a.length()), b.substring(0, b.length())),
					solution(a.substring(0, a.length()), b.substring(1, b.length())));
		}
	}

	private int max(int i, int j) {
		return i > j ? i : j;
	}
}