问题 5581 --[动归基础]最长公共子序列

5581: [动归基础]最长公共子序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 43  解决: 34
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][44kb]

题目描述

最长公共子序列 lcs.pas

【问题描述】

  一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1, x2,, xm>,则另一序列Z=<z1, z2,, zk>X的子序列是指存在一个严格递增的下标序列 <i1, i2,, ik>,使得对于所有j=1,2,,k


例如,序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列XY,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列XY的公共子序列。例如,若X=<A, B, C, B, D, A, B>Y=<B, D, C, A, B, A>,则序列<B, C, A>XY的一个公共子序列,序列<B, C, B, A>也是XY的一个公共子序列。而且,后者是XY的一个最长公共子序列,因为XY没有长度大于4的公共子序列。


  给定两个序列X=<x1, x2, , xm>Y=<y1, y2, , yn>,要求找出XY的一个最长公共子序列。

【输入格式】

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

【输出格式】

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

【输入样例】

ABCBDAB

BDCABA

【输出样例】

4

输入

输出

提示

来源

[提交][状态]