← 返回题单
题单练习 双序列型DP入门
← 上一题 下一题 →

A6974 | [模版]最长公共子序列

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定两个由小写拉丁字母组成的字符串 $s$ 和 $t$。请你找出这两个字符串的最长公共子序列的长度。

为了明确定义：

1. 子序列 (Subsequence)：如果字符串 $a$ 可以通过从字符串 $b$ 中删除若干个（可能是零个或全部）字符，且保持剩余字符的相对顺序不变而得到，则称 $a$ 是 $b$ 的子序列。
* 例如："ace" 是 "abcde" 的子序列，但 "ca" 不是 "abcde" 的子序列。
2. 公共子序列 (Common Subsequence)：如果序列 $z$ 既是 $s$ 的子序列，又是 $t$ 的子序列，则称 $z$ 为 $s$ 和 $t$ 的公共子序列。
3. 最长公共子序列 (LCS)：在 $s$ 和 $t$ 的所有公共子序列中，长度最长的那个序列。

你需要输出这个最长公共子序列的长度。

输入格式

第一行包含一个字符串 $s$ ($1 \le |s| \le 3000$)。
第二行包含一个字符串 $t$ ($1 \le |t| \le 3000$)。

输入保证两个字符串仅包含小写拉丁字母。

输出格式

输出一个整数，表示 $s$ 和 $t$ 的最长公共子序列的长度。

输入输出样例

输入 #1
abcvdefgh
bcefg
输出 #1
5
输入 #2
abacaba
acbda
输出 #2
4
输入 #3
abc
def
输出 #3
0
C++ 编辑器
输入
输出