时间限制：1秒　　内存限制：256M

---

【问题描述】

　　序列 \(x_1,x_2,...,x_m\) 的子序列，就是把其中的某些项删除后剩下的序列。例如”ABCBDAB”删除红色的字母后得到子序列“BCAB”。下面是更专业的定义：
　　我们称序列 \(Z= <z_1,z_2,...,z_k>\) 是序列 \(X= <x_1,x_2,...,x_m>\) 的子序列当且仅当存在 严格上升 的序列 \(<i_1,i_2,...,i_k>\)，使得对 \(j=1,2,...,k\) 有 \(x_{i_j}=z_j\)。比如 Z=<a,b,f,c> 是X=<a,b,c,f,b,c>的子序列。
　　现在给出两个序列 \(X\) 和 \(Y\)，你的任务是找到 \(X\) 和 \(Y\) 的最大公共子序列，也就是说要找到一个最长的序列 \(Z\)，使得 \(Z\) 既是 \(X\) 的子序列也是 \(Y\) 的子序列。最长公共子序列的英文缩写为 \(LCS\)。

【输入格式】

　　包含两行，每行是一个只含有英文字母的字符串。字符串长度不超过5000。

【输出格式】

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

【输入输出样例】

　Input

ABCBDAB
BDCABA

　Output

4

【数据限制】

　　字符串长度不超过5000。

【来源】

　　Mr.he