A7954.最长公共子序列

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

存在序列 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

    4

【普及组算法10】动态规划

0/18
首页