A6921. 最长公共子序列
编程题
普及-
知识点
题目描述
给定两个由小写英文字母组成的字符串 $S$ 与 $T$，请计算它们的最长公共子序列（LCS）长度。
公共子序列是指：从原字符串中删除若干（可为 $0$ 个）字符且不改变剩余字符相对顺序后得到的序列。
例如：$S=\texttt{abac}$、$T=\texttt{cab}$，它们的 $\text{LCS}$ 长度为 $2$（如 ab 或 ac），因为字符顺序不能改变。
公共子序列是指：从原字符串中删除若干（可为 $0$ 个）字符且不改变剩余字符相对顺序后得到的序列。
例如：$S=\texttt{abac}$、$T=\texttt{cab}$，它们的 $\text{LCS}$ 长度为 $2$（如 ab 或 ac），因为字符顺序不能改变。
输入格式
一行字符串 $S$
一行字符串 $T$
（均为小写英文字母，且不含空格）
一行字符串 $T$
（均为小写英文字母，且不含空格）
输出格式
输出一个整数，表示 $S$ 与 $T$ 的 $\text{LCS}$ 长度。
输入输出样例
输入 #1
abac cab
输出 #1
2
输入 #2
abc def
输出 #2
0
说明/提示
$1 \le |S|,|T| \le 2000$
对于样例一：
最长公共子序列为
对于样例二：
两个字符串显然没有公共子序列，故答案为 $0$。
对于样例一：
最长公共子序列为
ab，长度为 $2$。对于样例二：
两个字符串显然没有公共子序列，故答案为 $0$。