import java.util.*;

public class lcs {
    public static void main(String[] Args) {
        seq1 = "CGGGTAATGCA";
        seq2 = "GTAACCTGGAT";
        int n = seq1.length();
        int m = seq2.length();
        
        memo_table = new int[n + 1][m + 1];
        build_back_x = new int[n + 1][m + 1];
        build_back_y = new int[n + 1][m + 1];
        for (int[] tmp : memo_table)
            Arrays.fill(tmp, SENTINEL);
        
        
        System.out.println(lcs(0,0));
        
        
        for (int[] tmp : memo_table) 
            System.out.println(Arrays.toString(tmp));
        
        int first = 0;
        int second = 0;
        while (first < n && second < m) {
            
            
            int dx = build_back_x[first][second];
            int dy = build_back_y[first][second];
            
            if (dx == 1 && dy == 1) {
                System.out.print(seq1.charAt(first));
            }
            
            first += dx;
            second += dy;
        }
        System.out.println();
    }
    
    public static String seq1, seq2;
    
    // Memoization
    public static int[][] memo_table;
    public static int[][] build_back_x;
    public static int[][] build_back_y;
    public static int SENTINEL = -1;
    
    public static int lcs(int first, int second) {
        if (memo_table[first][second] != SENTINEL) {
            return memo_table[first][second];
        }
        int ans = 0;
        
        // Check for match
        if (first == seq1.length() || second == seq2.length()) {
            // Do Nothing: we are at the end
        } else if (seq1.charAt(first) == seq2.charAt(second)) {
            // We matched add 1 to answer
            // don't consider removing only one remove both
            ans = 1 + lcs(first + 1, second + 1);
            build_back_x[first][second] = 1;
            build_back_y[first][second] = 1;
        } else {
            ans = lcs(first + 1, second);
            build_back_x[first][second] = 1;
            build_back_y[first][second] = 0;
            
            int tmp = lcs(first, second + 1);
            if (ans < tmp) {
                ans = tmp;
                build_back_x[first][second] = 0;
                build_back_y[first][second] = 1;
            }
        }
        
        memo_table[first][second] = ans;
        return ans;
    }
}