U197280 【模板】最长公共子序列

题目背景

最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。字符串长度小于等于1000。

【题意】

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

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

比如：

$S_1$=abbccdss

$S_2$=aeebfcaadb

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

【输入格式】

两行，分别是字符串$S_1$和$S_2$（ 长度不大于1000）。

【输出格式】

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

【样例输入】

abbccdss
aeebfcaadb

【样例输出】

4