ac

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();

//        String s1 = "1A2C3D4B56";
//        String s2 = "B1D23CA45B6A";

        int n1 = s1.length();
        int n2 = s2.length();
        // s1
        // s2
        int[][] dp = new int[n2+1][n1+1];
        for(int i=0;i<=n1;i++){
            dp[0][i] = 0;
        }
        for(int i=0;i<=n2;i++){
            dp[i][0] = 0;
        }
        for(int i=0;i<n2;i++){
            // 已经有 dp[i][0....n2]
            // 当前求出 dp[i+1][1...j+1]
            for(int j=0;j<n1;j++){
                if(s2.charAt(i) == s1.charAt(j)){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }
                dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i+1][j]);
                dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j+1]);
            }
        }
        int s1Index = 0;
        int s2Index = 0;
        int maxLen = 0;
        for(int i=0;i<n2;i++){
            for(int j=0;j<n1;j++){
//                System.out.print(dp[i+1][j+1] + " ");
                if(dp[i+1][j+1] > maxLen){
                    maxLen = dp[i+1][j+1];
                    s1Index = j;
                    s2Index = i;
                }
            }
//            System.out.println();
        }
//        System.out.println(maxLen + " " + s1Index + " " + s2Index);
        int i = n2;
        int j = n1;
        int curLen = maxLen;
        String res = "";
        while (curLen > 0){
            if(dp[i][j] > dp[i-1][j] && dp[i][j] > dp[i][j-1]){
                res = s2.charAt(i-1) + res;
                curLen --;
                i--;
                j--;
            }else if(dp[i][j] == dp[i][j-1]){
                j--;
            }else if(dp[i][j] == dp[i-1][j]){
                i--;
            }
        }
        System.out.println(res);
    }

}

1A2C3D4B56
B1D23CA45B6A

"123456"和“12C4B6”都是最长公共子序列，任意输出一个。

 1A2C3D4B56
B
1
D
2
3
C
A
4
5
B
6
A

0 0 0 0 0 0 0 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 2 2 2 2 2 
1 1 2 2 2 2 2 2 2 2 
1 1 2 2 3 3 3 3 3 3 
1 1 2 3 3 3 3 3 3 3 
1 2 2 3 3 3 3 3 3 3 
1 2 2 3 3 3 4 4 4 4 
1 2 2 3 3 3 4 4 5 5 
1 2 2 3 3 3 4 5 5 5 
1 2 2 3 3 3 4 5 5 6 
1 2 2 3 3 3 4 5 5 6 

class Solution {
   /*
         "" a c e
      ""  0 0 0 0
       a  0 1 1 1
       b  0 1 1 1
       c  0 1 2 2
       d  0 1 2 2
       e  0 1 2 3
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length();
        int n2 = text2.length();
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        // dp[i][j]
        // s1[0..i] s2[0...j]
        int[] dp = new int[n2+1];
        int[] dpTmp = new int[n2+1];
        for(int i=1;i<=n1;i++){
            // 上一行的 dp[j-1]
            int last_pre_j_1 = dp[0];
            // 上一行的 dp[j]
            int last_pre_j = dp[1];
            // 遍历求解
            for(int j=1;j<=n2;j++){
                int tmpJ = 0;
                tmpJ = Math.max(tmpJ, last_pre_j);
                tmpJ = Math.max(tmpJ, dp[j-1]); // 当前的dp[j-1]
                if(s1[i-1] == s2[j-1]){
                    tmpJ = Math.max(last_pre_j_1 + 1, tmpJ);
                }
                // 更新
                last_pre_j_1 = dp[j];
                if(j < n2) {
                    last_pre_j = dp[j + 1];
                }
                dp[j] = tmpJ;
            }
        }
        return dp[n2];
    }
}

class Solution {
    /*
         "" a c e
      ""  0 0 0 0
       a  0 1 1 1
       b  0 1 1 1
       c  0 1 2 2
       d  0 1 2 2
       e  0 1 2 3
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length();
        int n2 = text2.length();
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        // dp[i][j]
        // s1[0..i] s2[0...j]
        int[] dp = new int[n2+1];
        int[] dpTmp = new int[n2+1];
        for(int i=1;i<=n1;i++){
            for(int k=0;k<=n2;k++){
                dpTmp[k] = dp[k];
            }
            // 更新
            for(int j=1;j<=n2;j++){
                dp[j] = Math.max(dp[j], dp[j-1]);
                dp[j] = Math.max(dp[j], dpTmp[j-1]);
                if(s1[i-1] == s2[j-1]){
                    dp[j] = Math.max(dpTmp[j-1] + 1, dp[j]);
                }
            }
        }
        return dp[n2];
    }
}