题目描述

一个字符串的子序列，是从原字符串中删除若干个字符后得到的字符串，剩余字符的相对顺序不能改变。

给定两个仅包含大写英文字母的字符串 $X$ 和 $Y$，求它们的最长公共子序列长度。

输入格式

第一行包含字符串 $X$。

第二行包含字符串 $Y$。

输出格式

输出一行一个非负整数，表示最长公共子序列长度。若两个字符串没有公共字符，输出 $0$。

样例

ABCBDAB
BDCABA

4

数据范围与提示

• 字符串仅包含大写英文字母
• $1 \le |X|,|Y| \le 1000$