题目描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=(x1,x2,…,xm),则另一序列Z=(z1,z2,…,zk)是X的子序列是指存在一个严格递增的下标序列(i1,i2,…,ik),使得对于所有j=1,2,…,k有:Xi=Zj
例如,序列Z=(B,C,D,B)是序X=(A,B,C,D,A,B)的子序列,相应的递增下标序列为(2,3,5,7)。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。若X=(A,B,C,B,D,A,B)和Y=(B,D,C,A,B,A),则序列(B,C,B,A)是X和Y的一个公共子序列。而且,是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。
对于给定两个串X和Y,编程输出最长公共子子序列的长度及最长公共子序列。
输入格式
共有两行,每行为一个由大写字母构成的长度不超过200的字符串,表示序列X和Y。
输出格式
第一行为一个非负整数,表示所求得的最长公共子序列的长度。若不存在公共子序列,则输出文件只有一行,输出一个整数0,否则在输出文件的第二行输出所求得的最长公共子序列。若符合条件的最长公共子序列不止一个,只需输出其中任意的一个。
样例
输入样例
ABCBDAB
BDCABA
输出样例
4
BCBA