A1647 | $最长公共子序列$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

存在序列 X 和 序列 Y，若有序列 Z 即是 X 的子序列，也是 Y 的子序列，则称 Z 是序列 X 和 序列 Y 的公共子序列。其中 X 和 Y 中，子序列最长的，则被称为 X 和 Y 的最长公共子序列。例如，若 X＝<A, B, C, B, D, A, B> 和 Y＝<B, D, C, A, B, A>，则序列 <B, C, A> 是 X 和 Y 的一个公共子序列, 序列 <B, C, B, A> 也是 X 和 Y 的一个公共子序列。而且，后者是 X 和 Y 的一个最长公共子序列。因为 X 和 Y 没有长度大于 4 的公共子序列。给定两个序列 X 和 Y，要求找出 X 和 Y 的一个最长公共子序列。

共有两行。每行为一个由大写字母构成的长度不超过 1000 的字符串，表示序列 X 和 Y。

一行为一个非负整数，表示所求得的最长公共子序列的长度。若不存在公共子序列．则输出文件仅有一行输出一个整数 0。

输入 #1

ABCBDAB
BDCABA

输出 #1

C++ 编辑器

输入

输出