#AT6. LCS
LCS
[F] LCS(dp_f)
来源: AtCoder Educational DP Contest - Problem F 原题时限:2 秒 / 内存:1024 MB
题目描述
给定两个字符串 与 ,求一个最长的字符串,使它同时是 与 的子序列。
提示
字符串 的子序列是指:从 中删去零个或多个字符后,将剩余字符按原顺序拼接得到的字符串。
输入格式
输入由标准输入按以下格式给出:
s
t
输出格式
输出一个最长的、同时是 与 子序列的字符串。若有多个满足条件的字符串,输出任意一个均可。
数据范围
- 与 均仅由小写英文字母组成。
样例 1
输入:
axyb
abyxb
输出:
axb
样例 2
输入:
aa
xayaz
输出:
aa
样例 3
输入:
a
z
输出:
样例 4
输入:
abracadabra
avadakedavra
输出:
aaadara
注: 本题答案不唯一(最长公共子序列可能有多解),采用 Special Judge:只要输出的是 与 的某个最长公共子序列即判为正确(空串也算合法答案)。