import java.io.*;

class LongestCommonSubsequence {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("Enter length of Sequence 1: ");
        int len1 = Integer.parseInt(reader.readLine());

        System.out.println("Enter Sequence 1:");
        String seq1 = reader.readLine();

        System.out.print("Enter length of Sequence 2: ");
        int len2 = Integer.parseInt(reader.readLine());

        System.out.print("Enter Sequence 2: ");
        String seq2 = reader.readLine();

        // dpTable[i][j] = length of LCS of seq1[0..i-1] and seq2[0..j-1]
        int[][] dpTable      = new int[50][50];
        // directionTable[i][j] records how we got to dpTable[i][j]:
        //   '' means seq1[i] == seq2[j] (diagonal -- character is in LCS)
        //   '|' means we took dpTable[i-1][j]  (from above)
        //   '-' means we took dpTable[i][j-1]  (from left)
        char[][] directionTable = new char[len1 + 1][len2 + 1];

        // Base cases: LCS of empty prefix is 0
        for (int i = 0; i <= len1; i++) dpTable[i][0] = 0;
        for (int j = 0; j <= len2; j++) dpTable[0][j] = 0;

        System.out.println("\nDP Table:");

        // Fill the DP table row by row
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (i == 0 || j == 0) {
                    // Print border cells (value 0) without computing LCS
                    System.out.print(dpTable[i][j]);
                    continue;
                }

                if (seq1.charAt(i) == seq2.charAt(j)) {
                    // Characters match: extend the LCS by 1
                    directionTable[i][j] = '';
                    dpTable[i][j]        = dpTable[i - 1][j - 1] + 1;
                    System.out.print(directionTable[i][j] + dpTable[i][j]);
                } else if (dpTable[i - 1][j] >= dpTable[i][j - 1]) {
                    // LCS from above is at least as long
                    directionTable[i][j] = '|';
                    dpTable[i][j]        = dpTable[i - 1][j];
                    System.out.print(directionTable[i][j] + dpTable[i][j]);
                } else {
                    // LCS from the left is longer
                    directionTable[i][j] = '-';
                    dpTable[i][j]        = dpTable[i][j - 1];
                    System.out.print(directionTable[i][j] + dpTable[i][j]);
                }
            }
            System.out.println();
        }

        // Traceback: follow '' arrows to collect LCS character indices
        int   row         = len1 - 1;
        int   col         = len2 - 1;
        int[] lcsIndices  = new int[10];   // stores row indices of matched characters
        int   lcsLength   = 1;             // 1-indexed counter

        System.out.print("\nLongest Common Subsequence: ");

        while (row > 0 || col > 0) {
            if (directionTable[row][col] == '') {
                // Diagonal arrow: this position is part of the LCS
                lcsIndices[lcsLength] = row;
                lcsLength++;
                row--;
                col--;
            } else if (directionTable[row][col] == '|') {
                // Arrow from above: move up
                row--;
            } else {
                // Arrow from left: move left
                col--;
            }
        }

        // Print LCS characters in forward order (lcsIndices was filled in reverse)
        for (int i = lcsLength - 1; i > 0; i--) {
            System.out.print(seq1.charAt(lcsIndices[i]));
        }
        System.out.println();
    }
}