题目描述

给定两个字符串 $s$ 和 $t$，请找出一个同时是 $s$ 和 $t$ 的子序列、并且长度最大的字符串。

一个字符串的子序列，是从这个字符串中删除零个或多个字符后，将剩余字符按照原来的先后顺序连接得到的字符串。被保留的字符不一定连续。

如果有多个最长公共子序列，输出其中任意一个即可。

输入格式

输入共两行。

第一行包含字符串 $s$。

第二行包含字符串 $t$。

输出格式

输出一行，包含 $s$ 和 $t$ 的一个最长公共子序列。

如果最长公共子序列为空，输出一个空行。请输出子序列本身，而不是它的长度。

输入样例 #1

axyb
abyxb

输出样例 #1

axb

样例解释 #1

axb 和 ayb 都是这两个字符串的最长公共子序列，输出其中任意一个均正确。

输入样例 #2

aa
xayaz

输出样例 #2

aa

输入样例 #3

a
z

输出样例 #3

样例解释 #3

两个字符串没有相同的字符，因此最长公共子序列是空字符串，输出为空行。

数据范围

$1\le |s|,|t|\le 3000$。

$s$ 和 $t$ 均只包含小写英文字母。

来源

洛谷 AT_dp_f · 原题