A94834.[模版]最长公共子序列

给定两个由小写拉丁字母组成的字符串 $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$ 的最长公共子序列的长度。

说明

在第一个样例中，最长公共子序列是 "bcefg"，其长度为 5。
在第二个样例中，最长公共子序列是 "acba"（或者 "acda"），其长度为 4。
在第三个样例中，没有公共字符，长度为 0。