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;
    }
}