同和新媒体矩阵官网同和视频矩阵同和素材矩阵

登录 | 立即注册

同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1901_算法设计例题：最长公共子序列（DP）

2022-5-16 18:17| 发布者: Hocassian| 查看: 45| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504128827200-Problem List-采集的数据-后羿采集器.html

Pro.ID

1901

Title

算法设计例题：最长公共子序列（DP）

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1901

AC

664

Submit

2448

Ratio

27.12%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 X = { x₁，x₂，…，x_m }，则另一序列Z ={ z₁，z₂，…，z_k }，X 的子序列是指存在一个严格递增下标序列{ i₁，i₂，…，i_k }，使得对于所有 j = 1，2，…，k ，有 z_j = x_{i_j}

给出两个字符序列 X 和 Y ，求出它们的最长公共子序列。

输入

输入的第一行为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是字符串 X ，第二行是字符串 Y。X 和 Y 只包含大写字母，且长度不大于1000。

输出

Description

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 X = { x₁，x₂，…，x_m }，则另一序列Z ={ z₁，z₂，…，z_k }，X 的子序列是指存在一个严格递增下标序列{ i₁，i₂，…，i_k }，使得对于所有 j = 1，2，…，k ，有 z_j = x_{i_j}

给出两个字符序列 X 和 Y ，求出它们的最长公共子序列。

Input

输入的第一行为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是字符串 X ，第二行是字符串 Y。X 和 Y 只包含大写字母，且长度不大于1000。

Output

对应每个测试样例输出一行，只有一个整数，表示字符串 X 和字符串 Y 的最长公共子序列的长度。

Sample Input

2
ABCDE
ACE
AAABBBCCC
AABBCC

Sample Output

3
6

Author

陈奕平Eapink & 陈渝林

样例输入

2
ABCDE
ACE
AAABBBCCC
AABBCC

样例输出

3
6

提示

陈奕平Eapink & 陈渝林

作者

最新评论

相关分类

返回顶部