#1508. 最长公共子序列

最长公共子序列

题目描述

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X(x1x2xm)\red{X=(x_{1},x_{2},…,x_{m} )},则另一序列Z(z1z2zk)\red{Z=(z_{1},z_{2},…,z_{k} )}是X的子序列是指存在一个严格递增的下标序列(i1i2ik)\red{(i_{1},i_{2},…,i_{k} )},使得对于所有j12k\red{j=1,2,…,k}有:XiZj\red{X_{i}=Z_{j}}

例如,序列Z=(B,C,D,B)\red{Z=(B,C,D,B)}是序X=(A,B,C,D,A,B)\red{X=(A,B,C,D,A,B)}的子序列,相应的递增下标序列为(2,3,5,7)\red{(2,3,5,7)}。给定两个序列X\red{X}Y\red{Y},当另一序列Z\red{Z}既是X\red{X}的子序列又是Y\red{Y}的子序列时,称Z\red{Z}是序列X\red{X}Y\red{Y}的公共子序列。若X=(A,B,C,B,D,A,B)\red{X=(A,B,C,B,D,A,B)}Y=(B,D,C,A,B,A)\red{Y=(B,D,C,A,B,A)},则序列(B,C,B,A)\red{(B,C,B,A)}X\red{X}Y\red{Y}的一个公共子序列。而且,是X\red{X}Y\red{Y}的一个最长公共子序列,因为X\red{X}Y\red{Y}没有长度大于4\red{4}的公共子序列。

对于给定两个串X\red{X}Y\red{Y},编程输出最长公共子子序列的长度及最长公共子序列。

输入格式

共有两行,每行为一个由大写字母构成的长度不超过200\red{200}的字符串,表示序列X\red{X}Y\red{Y}

输出格式

第一行为一个非负整数,表示所求得的最长公共子序列的长度。若不存在公共子序列,则输出文件只有一行,输出一个整数0\red{0},否则在输出文件的第二行输出所求得的最长公共子序列。若符合条件的最长公共子序列不止一个,只需输出其中任意的一个。

样例

输入样例

ABCBDAB
BDCABA

输出样例

4
BCBA