题目描述

给定两个字符串 $s$ 与 $t$，请输出它们最长的公共子序列的长度。

子序列，是由原字符串的全部或部分字符组成的新序列，这些字符在原序列中不必连续，但要保持在原序列中的顺序。空序列也是一种子序列。

所谓公共子序列，就是 $s$ 与 $t$ 共同拥有的子序列。

所谓最长公共子序列，就是所有公共子序列中最长的子序列。

输入格式

• 第一行：一个字符串 $s$
• 第二行：一个字符串 $t$

输出格式

• 单个整数：表示最长公共子序列的长度

apple
banana

1

aabbcc
abcabc

4

数据范围

设 $n$ 表示 $s$ 的长度，$m$ 表示 $t$ 的长度

• $30\%$ 的数据，$1\leq n, m\leq 10$
• $60\%$ 的数据，$1\leq n, m\leq 200$
• $100\%$ 的数据，$1\leq n, m\leq 3000$
• 保证 $s$ 与 $t$ 只包含英文字母。