1875: 最长公共子序列

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：23 Solved：15

Description

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

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

    比如：

        S1:='abbccdss'

        S2:='aeebfcaadb'

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

Input

读入两行，分别是S1和S2（ 长度不大于500）。

Output

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

Sample Input Copy 

abbccdss
aeebfcaadb

Sample Output Copy 

4