题目描述

小猿和小码来到了一个奇怪的糖果店，在挑选糖果时，他们每人需要提前把想要的糖果的名字首字母写下来分别交给店长。店长会仔细对比两个人写的内容，只有两个人挑的是一样的糖果并且挑选的先后顺序也要一样才算数。最终小猿和小码每人最多可以获得多少糖果呢？

换句话说，给定两个字符串，求它们的最长公共子序列的长度。

输入格式

两行，每行一个字符串，分别表示小猿和小码写的糖果名字首字母，均由小写字母组成。

输出格式

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

样例

abcbdab
bdcaba

4

数据范围

• 字符串长度不超过 $100$。
• 字母范围：小写字母 a $\sim$ z。