题目描述

给定两个仅由小写英文字母组成的字符串 $A$ 和 $B$，求它们的最长公共子序列的长度。

子序列 是指从原字符串中删除任意多个字符（也可以不删除）后，剩余字符保持原有顺序组成的序列。注意：子序列不要求字符连续。

例如，对于字符串 abcde：

• ace 是它的子序列；
• aec 不是它的子序列，因为字符顺序改变了。

最长公共子序列（Longest Common Subsequence，LCS）是指两个字符串共有的子序列中最长的那个。

输入格式

共两行：

• 第一行一个字符串 $A$；
• 第二行一个字符串 $B$。

字符串中仅包含小写英文字母，且长度均不超过 $1000$。

输出格式

输出一个整数，表示字符串 $A$ 和 $B$ 的最长公共子序列的长度。

样例

abcde
ace

3

aggtab
gxtxayb

4

introductiontoalgorithms
olympiadinformatics

8

说明/提示

样例 1 解释

字符串 abcde 和 ace 的最长公共子序列是 ace，其长度为 3。

数据范围

• 对于 $30\%$ 的数据，$|A|, |B| \le 10$
• 对于 $60\%$ 的数据，$|A|, |B| \le 100$
• 对于 $100\%$ 的数据，$1 \le |A|, |B| \le 1000$，字符串仅由小写英文字母 a ~ z 组成。