2423 - 字符串的最长公共子序列

题目描述

给定 2 个字符串 s_1s_2 ,如果 s_2 中所有的字符,在 s_1 中都存在,且在 s_1 中的下标顺序是严格递增的,那么我们将s2称之为s1的子序列。

比如:

s_1 = "abcdef"s_2 = "bdf",则 s_2 按上述条件是 s_1 的子序列。

现给你两个字符串 s_1s_2 ,请问它们的最长公共子序列的长度是多少?

输入

输入包含多组测试数据,第 1 行有一个整数 n 表示测试数据的组数(不超过 100 组)。

接下来 n 行,每行为两个仅包含小写字母的字符串,由 1 个空格分隔。每个字符串的长度不超过 100

输出

对于每组输入,输出两个字符串的最长公共子序列的长度。

样例

输入

3
abcfbc abfcab
programming contest 
abcd mnp

输出

4
2
0
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 150
通过人数 80
金币数量 1 枚
难度 入门


上一题 下一题