1183 - 最长公共子序列

 若给定序列X={x1,x2,,xm},则另一序列Z={z1,z2,,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,,ik}使得对于所有j=1,2,,k有:zj=xij。例如,序列Z={BCDB}是序列X={ABCBDAB}的子序列,相应的递增下标序列为{2357}

给定2个序列XY,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列XY的公共子序列。

给定2个序列X={x1,x2,,xm}Y={y1,y2,,yn},找出XY的最长公共子序列。

输入

为保障统计正确,需在输入字符数组x和y的第一个字符设置标示,该字符不参与统计

第一行输入序列x。

第二行输入序列y。

输出

第一行输出最大子串长度。

第二行输出最大子串。

样例

输入

@thiscbook
#tisnook

输出

6
tisook
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题