1409-孩子有多像爸爸


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:7 提交数:31 难度:4


题目描述:

假设爸爸对应的基因序列为X={x1x2x3…,xm},孩子对应的基因序列Y={y1y2y3…,yn},那么怎么找到他们有多少相似的基因呢?

如果按照严格递增的顺序,从爸爸的基因序列X中取出一些值,组成序列Z={xi1xi2xi3…,xik},其中下标{i1i2i3…,ik }是一个严格递增的序列。那么就说ZX的子序列,Z中元素的个数就是该子序列的长度。

XY的公共子序列是指该序列既是X的子序列,也是Y的子序列。

最长公共子序列问题是指:给定两个序列X={x1x2x3…,xm}Y={y1y2y3…,yn},找出XY的一个最长的公共子序列。


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个字符串s1(0<字符串长度<1000)。
第2行,是一个字符串s2(0<字符串长度<1000)。

输出描述:

对于每一组输入,输出s1和s2的最长公共子序列长度。
每组的输出占一行。

样例输入:

2
ABCADAB
BACDBA
ACDEF
ADF

样例输出:

4
3

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!