← 返回题目

题库练习字符串的最长公共子序列

← 上一题下一题 →

A71363 | $字符串的最长公共子序列$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

给定 2 个字符串 s_1 和 s_2 ，如果 s_2 中所有的字符，在 s_1 中都存在，且在 s_1 中的下标顺序是严格递增的，那么我们将 s2 称之为 s1 的子序列。 比如： s_1 = "abcdef" ， s_2 = "bdf" ，则 s_2 按上述条件是 s_1 的子序列。 现给你两个字符串 s_1 和 s_2 ，请问它们的最长公共子序列的长度是多少？

输入格式

输入包含多组测试数据，第 1 行有一个整数 n 表示测试数据的组数（不超过 100 组）。 接下来 n 行，每行为两个仅包含小写字母的字符串，由 1 个空格分隔。每个字符串的长度不超过 100 。

输出格式

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

输入输出样例

输入 #1

3
abcfbc abfcab
programming contest 
abcd mnp

输出 #1

4
2
0

C++ 编辑器

输入

输出