LCS

최장 공통 부분 수열(LCS) 문제는 두 개의 문자열에서 순서대로 겹치는 문자가 최대 몇 개인지 구하는 문제이다.

ex) ABCBDAB와 BDCABA 에서 LCS는 BCAB나 BDAB나 BCDB 이다.

앞에서부터 겹치는 것들을 찾아서 문자열을 만들 때 그것이 가장 길다면 LCS가 되는 것이다.

두문자열이 모두 0번째일때, 두 문자열의 값이 같을 때, 두 문자열의 값이 같이 않을 때

3가지 경우로 나누어 생각 하면된다.

LCS 배열 마지막에는 LCS의 길이를 볼 수 있다.

길이가 아닌 LCS 에 해당하는 수열을 찾는 방법은 길이가 변하는 시점이 공통 부분인 것은 이미 알고 있기 때문에 그림과 같이 대각선인 시점을 체크하면 된다.

3개의 문자열을 통해 LCS를 구해야한다면 2차원 배열에서 3차원 배열로 바꿔주면 된다.

import java.io.FileInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class LCS1 {

    static public int LCSCount(char[] first, char[] second) {
        int[][] LCS = new int[1001][1001];

        for (int i=1; i<=first.length; i++){
            for (int j=1; j<=second.length; j++) {
                if(first[i-1] == second[j-1]) {
                    LCS[i][j] = LCS[i-1][j-1] + 1;
                } else {
                    LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
                }
            }
        }

        return LCS[first.length][second.length];
    }

    static public String LCSString(char[] first, char[] second) {
        int[][] LCS = new int[1001][1001];
        String[][] memo = new String[1001][1001];

        for (int i=1; i<=first.length; i++){
            for (int j=1; j<=second.length; j++) {
                if(first[i-1] == second[j-1]) {
                    LCS[i][j] = LCS[i-1][j-1] + 1;
                    memo[i][j] = "diagonal";
                } else {
                    LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
                    if (LCS[i][j] == LCS[i-1][j]) {
                        memo[i][j] = "up";
                    } else {
                        memo[i][j] = "left";
                    }
                }
            }
        }

        int a = first.length;
        int b = second.length;
        StringBuffer sb = new StringBuffer();
        while (memo[a][b] != null) {
            if (memo[a][b] == "diagonal") {
                sb.append(first[a-1]);
                a--; b--;
            } else if (memo[a][b] == "up"){
                a--;
            } else if (memo[a][b] == "left") {
                b--;
            }
        }

        return sb.reverse().toString();
    }

    static public void main (String args[]) throws Exception {
        System.setIn(new FileInputStream("src/input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int tc=1; tc<=T; tc++) {
            char[] first = br.readLine().toCharArray();
            char[] second = br.readLine().toCharArray();

            bw.write(String.valueOf(LCSCount(first, second)));
            bw.newLine();

            bw.write(String.valueOf(LCSString(first, second)));
            bw.newLine();
        }

        bw.flush();
        bw.close();
        br.close();
    }
}