//动态规划（Ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ）的最长公共子序列问题（Lｏｎｇｅｓｔ　ｃｏｍｍｏｎ　ｓｕｂｓｅｑｕｅｎｃｅ）

//原理参考《算法导论》书

import java.util.Scanner;public class LCS {    public static void main(String[] args) {        Scanner sc=new Scanner(System.in);        String s1=sc.nextLine();        String s2=sc.nextLine();        int len1=s1.length();        int len2=s2.length();        int c[][]=new int[len1+1][len2+1];        int b[][]=new int[len1+1][len2+1];        for(int i=0;i<=len1;i++){            for(int j=0;j<=len2;j++){                if(i==0||j==0){                    c[i][j]=0;                }else if(s1.charAt(i-1)==s2.charAt(j-1)){                    c[i][j]=c[i-1][j-1]+1;                    b[i][j]=1;//表示左向上箭头                }else if(c[i-1][j]>=c[i][j-1]){                    c[i][j]=c[i-1][j];                    b[i][j]=2;//表示↑                }else{                    c[i][j]=c[i][j-1];                    b[i][j]=3;//表示←                }            }        }        //直接输出表c,c[i,j]表示Xi和Yj的LCS的长度        /*        for(int i=0;i<=len1;i++){            for(int j=0;j<=len2;j++){                System.out.print(c[i][j]+" ");            }            System.out.println();        }        */                //直接输出表b,b[i,j]表示子问题最优解的指向        /*        for(int i=0;i<=len1;i++){            for(int j=0;j<=len2;j++){                System.out.print(b[i][j]+" ");            }            System.out.println();        }        */                System.out.println(c[len1][len2]);        printLCS(b,s1,len1,len2);//调用方法printLCS，打印LCS的元素        sc.close();    }        /**     * 封装一个方法，打印LCS的元素（利用递归过程，逆序依次打印）     * @param b 子问题最优解的指向     * @param str 一个输入序列X     * @param m 输入序列X的长度     * @param n 输入序列Y的长度     */    public static void printLCS(int b[][],String str,int m,int n){                if(m==0||n==0){                    return;                }                if(b[m][n]==1){                    printLCS(b,str,m-1,n-1);                    System.out.print(str.charAt(m-1)+" ");                }else if(b[m][n]==2){                    printLCS(b,str,m-1,n);                }else{                    printLCS(b,str,m,n-1);                }//直接用递归，之前用了for循环，一直输出好多元素.....    }}