TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8557
  • 题目
  • P8557最长公共子序列
    限制 : 时间限制 : 1000 MS   空间限制 : 25600 KB
    问题描述

    一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列 X=<x1,x2,…,xm>,则另一序列 Z=<z1,z2,…,zk>是 X 的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>,使得对于所有j=1,2,…,k 有: Xij=Zj 例如,序列 z=<B,C,D,B>是序列 X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列 X 和 Y,当序列 Z 既是 X 的子序列又是 Y的子序列时,称 z 是序列 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=<x1,x2,…,xm>和 Y=<y1,y2….yn>.要求找出 X 和 Y 的一个最长公共子序列。

    输入格式

    输入文件共有两行。每行为一个由大写字母构成的长度不超过 200 的字符串,表示序列 X 和 Y。

    输出格式

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

    样例输入

    ABCBDAB 
    BDCABA

    样例输出

    4