1110: 最长公共子序列
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:7
解决:4
题目描述
若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。
给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
输入
为保障统计正确,需在输入字符数组x和y的第一个字符设置标示,该字符不参与统计
第一行输入序列x。
第二行输入序列y。
输出
第一行输出最大子串长度。
第二行输出最大子串。
样例输入 复制
@thiscbook
#tisnook
样例输出 复制
6
tisook