当前没有测试数据。

题目描述

给定两个字符串 $S$ 和 $T$，求它们的最长公共子序列的长度。

子序列是指从原字符串中删除一些字符（可以不删除，也可以全部删除）后，不改变剩余字符相对位置形成的新字符串。

输入格式

第一行输入字符串 $S$。

第二行输入字符串 $T$。

输出格式

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

样例 #1

输入

ABCBDAB
BDCABA

输出

4

样例说明

样例 1 解释

最长公共子序列可以是 BCBA、BDAB 或 BCAB，长度为 4。

数据范围

对于 $100\%$ 的数据，字符串长度不超过 $1000$，仅包含大写字母。