P10174: 最长公共子序列LCS
传统题
1.000s
时间限制
128MB
内存限制
3 提交
2 解决
【题目描述】
最长公共子序列LCS（Longest Common Subsequence）
【LCS开篇案例】
序列：X={A,B,C,B,D,A,B}
序列：Y={B,C,D,B,A}
序列：Z={B,C,D,B}
序列：W={B,C,D}
Z是（X与Y）的最长公共子序列（Longest-Common-Subsequence），而W虽然是X与Y的公共子序列，但是不是最长的!
【LCS晦涩定义】
给定一个序列X={x1,x2,x3...xm},另一个序列Z={z1,z2,z3...zk}为子序列，如果存在X的
一个严格递增下标序列<i1,i2,i3,i4...ik>，使得所有的j=1,2,...,k,有x[i<j>]=z[j]
例如，Z={B,C,D,B}是X={A,B,C,B,D,A,B}一个最长子序列，相应的下标序列为<2,3,5,7>
如果Z同时是Y的最长子序列，那么Z就是X与Y的最长公共子序列
【输入样例】
ABCBDAB
BDCABA
【输出样例】
4
【说明】 输入两行字符，输出LCS长度