题目描述

给定两个字符串，求解这两个字符串的最长非连续（允许连续或非连续）的公共子序列的长度（Longest Common Sequence）。
比如字符串1：BDCABA；字符串2：ABCBDAB。
则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA

输入要求

输入2行，每行一个字符串；字符串长度<1000。

输出要求

输出两个字符串的最长非连续的公共子序列的长度。

输入样例

lynfzqmguhrjnckxzwteokiutsbimbbxowffi
ezukifbyiyvrzderlheqdulgaigtcdehlndrykcrozmayalhlnaebkjzqkitpkmgwqojksonsrngwddswomynbxoydjjrhftlmxixoutdxhsexcshdwgbwzxljdlignqpkmzrpnxdvacxjkgcczakbkolcbasjfesklxujdwnuiocpxidyxstalevkjrgbizfyphxqfathiqaivfgyyialeelpiyxkwemxcwqstqjdsdfujtpfgzwawuligvhyhuqsvnmvpcqzpoaaqlfmccckyppzvwmeplivbx

输出样例

27

提示

来源

NBU OJ