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