问题 1894. -- 最长公共子序列LCS

1894: 最长公共子序列LCS

时间限制: 1 Sec  内存限制: 128 MB
提交: 22  解决: 18
[提交][状态][讨论版]

题目描述

给出两个字符串A、B,求A与B的最长公共子序列(子序列不要求是连续的)。比如两个串为:abcicba 和 abdkscab,则 ab是两个串的子序列,abc也是,abca也是,其中abca是这两个字符串最长的子序列。

输入

第1行:字符串A 
第2行:字符串B 
(A,B的长度 <= 500)

输出

输出最长的公共子序列的长度

样例输入

abcicba
abdkscab

样例输出

4

提示

来源

[提交][状态]