5814: 4.3 孩子有多像爸爸
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：71
解决：36
题目描述
假设爸爸对应的基因序列为 X = {x1, x2, x3 ... xm}， 孩子对应的基因序列 Y = {y1, y2, y3 ... ym}， 那么怎么找到他们有多少相似的基因呢？
如果按照严格递增的顺序，从爸爸的基因序列 X中取出一些值，组成序列 Z = {xi1, xi2, xi3 ... , xik},其中下标{i1, i2, i3 ... ik}是一个严格递增的序列，那么就说 Z 是 X 的子序列， Z 中元素的个数就是该子序列的长度。
X 和 Y 的公共子序列是指该序列即是 X 的子序列，也是 Y 的子序列。
最长公共子序列问题是指：给定两个序列 X = {x1, x2, x3, ... , xm} 和 Y = {y1, y2, y3 ... yn}， 找出 X 和 Y 的一个最长的公共子序列。
如果按照严格递增的顺序，从爸爸的基因序列 X中取出一些值，组成序列 Z = {xi1, xi2, xi3 ... , xik},其中下标{i1, i2, i3 ... ik}是一个严格递增的序列，那么就说 Z 是 X 的子序列， Z 中元素的个数就是该子序列的长度。
X 和 Y 的公共子序列是指该序列即是 X 的子序列，也是 Y 的子序列。
最长公共子序列问题是指：给定两个序列 X = {x1, x2, x3, ... , xm} 和 Y = {y1, y2, y3 ... yn}， 找出 X 和 Y 的一个最长的公共子序列。
输入
样例组数
t （0 < t < 100）
输入字符串 ( 字符串长度小于1000）
S1
输入字符串
S2
t （0 < t < 100）
输入字符串 ( 字符串长度小于1000）
S1
输入字符串
S2
输出
最长公共子序列的长度
d
d
样例输入 复制
1
ABCADAB
BACDBA样例输出 复制
4