2018: 最长公共子序列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

ABCBDAB

BDCABA

4