题目描述

给出两个字符串 $S1$ 和 $S2$ 求它们最长公共子序列的长度。

什么是最长公共子序列呢？

比如：

$S1=\texttt{abbccdss}$

$S2=\texttt{aeebfcaadb}$

那么 $S1$ 和 $S2$ 的最长公共子序列就是：$\texttt{abcd}$。 这个说明最长公共子序列强调位置的前后关系不变，但不在乎是否连续。最长公共子序列不唯一。

输入格式

两行，分别是字符串 $S1$ 和 $S2$。

输出格式

输出一个整数，即为最长公共子序列的长度。

abbccdss
aeebfcaadb

4

数据规模与约定

$|S1|,|S2|\le 1000$