T814453 【P1357】最长公共子序列（LCS）

子串 与 子序列 给定一个字符串，例如 "abcde"： 子串：原字符串中连续的一段字符。例如 "bcd"、"cde" 是子串，但 "ace" 不是（因为它在原串中不连续）。 子序列：从原字符串中删除若干个（可以是 0 个）字符后，剩余字符保持原有相对顺序拼接得到的字符串，不要求连续。例如 "ace"、"abe"、"bd" 都是 "abcde" 的子序列。 简单来说：子串要求连续，子序列只要求顺序不变，允许跳字符。子串一定是子序列，反之不成立。

给定两个字符串A和B，求它们的最长公共子序列（Longest Common Subsequence, LCS）的长度，即：找到一个字符串 S，使得S既是A的子序列，又是B的子序列，且S的长度最大，输出这个最大长度。

第一行输入字符串A 第二行输入字符串B

输出一个整数，表示字符串A和字符串B的最长公共子序列的长度。

对于$100 \%$的数据： $1 \le$ 字符串A、字符串B的长度 $\le 5000$，同时字符串中是由大写英文字母（'A' - 'Z'）和小写英文字母（'a' - 'z'）组成，不包含其它字符