挑选糖果

题目描述

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

输入格式

两行，每行一个字符串，分别表示小童和小美糖果名字的首字母，字母小写，字母可以重复。（字母范围：$a \sim z$，单个字符串长度 $\le 100$）

输出格式

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

样例输入 #1

abcbdab
bdcaba

样例输出 #1

4

数据范围

字符串仅含小写字母 $a \sim z$，单个字符串长度不超过 $100$。

知识点与难度

本题涉及的知识点（线性DP、最长公共子序列 LCS）从属于 GESP七级，难度等级：⭐⭐⭐。

测试点分布