LCS (최장공통수열)

Longest Common Subsequence

두 문자열(수열)이 주어졌을 때, 부분공통수열 중 가장 긴 수열 찾기
연속적이지 않아도 됨

1. 두 문자열을 배열로 표현한다.
2. DP[i][j]에 A문자열의 i번째 문자까지, B문자열의 j번째 문자까지 같은 문자의 총 개수를 저장한다.
3. A[i] = B[j]인 경우 A0~Ai와 B0~Bj가 모두 업데이트 되므로 DP[i-1][j-1]에 1을 더해준다.
4. 만약 다른 경우 둘 중 큰 값으로 업데이트한다.

문자열을 직접 출력하려면?
가장 마지막에서 부터 원점까지 역추적한다.

static void LCS(){
    for(int i=1; i<=a.length; i++) {
    	for(int j=1; j <= b.length; j++) {
    	    if(a[i-1] == b[j-1])
            	dp[i][j] = dp[i-1][j-1] + 1;
            else
        	dp[i][j] - Math.max(dp[i-1][j], dp[i][j-1]);
    	}
    }
    
    // LCS의 길이
    int length = dp[a.length][b.length];
    
    int i = a.length;
    int j = b.length;
    
    ArrayDeque<Character> stack = new ArrayDeque<>();
    
    while(dp[i][j] > 0) {
        if(dp[i][j] == dp[i][j-1]) {
            j--;
        } else if(dp[i][j] == dp[i-1][j]) {
            i--;
        } else {
        	// 대각선에서 온것
            stack.push(a[i-1]);
            i--;
            j--;
        }
    }
    
    // stack을 거꾸로 출력
 }