3030 - 最长公共子序列
时间限制 : 1 秒
内存限制 : 128 MB
子序列为原序列删除部分字符之后剩下的序列，或者说，子序列是从原序列中取出部分字符，并保持原有先后顺序组成的序列。如果序列Z同时为X和Y的子序列，则称Z为X和Y公共子序列。比如X=abcbdab，Y=bdcaba，则Z=bcba为X和Y的一个公共子序列。 给定序列X和Y，求出X和Y的最长公共子序列的长度。
输入
输入两行，分别包含一个字符串，仅含有小写字母。
输出
最长公共子序列的长度。
样例
输入
abcdgfehca hgibdfahc
输出
5
提示
样例中，最长公共子序列为bdfhc
数据规模和约定
对20%的数据，字符串长度小于等于30。
对100%的数据，字串长度小于等于1000。
来源
动规专题