问题 m: 最大公共子序列(动态规划)

问题 m: 最大公共子序列(动态规划)

时间限制: 1 Sec  内存限制: 128 MB
提交: 2092  解决: 815
[提交][状态][讨论版][命题人:]

题目描述

若给定序列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的最长公共子序列。

输入

输入包括两行,每行表示一个字符串。

输出

输出包括一个字符串和一个整数,其中前面的字符串表示最大公共子序列,后面的数字为公共子序列的长度。

样例输入

abcbdab
bfcdgbe

样例输出

bcdb 4

提示

[提交][状态]