503 - 最长公共子序列(LCS)

给定两个字符串序列X、Y,长度不超过5000,求出两个序列的最长公共子序列长度。注意:子序列不是子串,不要求连续,例如两个字符串"cnblogs"和"belong"的公共子序列为"blog"。可以发现,最长公共子序列是不唯一的,但是长度一定是唯一的。

输入

输入包含两个字符串,分别表示XY

输出

输出它们最长公共子序列的长度。

样例

输入

cnblogs
belong

输出

4
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题