#AT6. LCS

LCS

[F] LCS(dp_f)

来源: AtCoder Educational DP Contest - Problem F 原题时限:2 秒 / 内存:1024 MB

题目描述

给定两个字符串 ss 与 tt,求一个最长的字符串,使它同时是 ss 与 tt 的子序列。

提示

字符串 xx 的子序列是指:从 xx 中删去零个或多个字符后,将剩余字符按原顺序拼接得到的字符串。

输入格式

输入由标准输入按以下格式给出:

s
t

输出格式

输出一个最长的、同时是 ss 与 tt 子序列的字符串。若有多个满足条件的字符串,输出任意一个均可。

数据范围

  • ss 与 tt 均仅由小写英文字母组成。
  • 1≤∣s∣,∣t∣≤30001 \le |s|, |t| \le 3000

样例 1

输入:

axyb
abyxb

输出:

axb

样例 2

输入:

aa
xayaz

输出:

aa

样例 3

输入:

a
z

输出:


样例 4

输入:

abracadabra
avadakedavra

输出:

aaadara

注: 本题答案不唯一(最长公共子序列可能有多解),采用 Special Judge:只要输出的是 ss 与 tt 的某个最长公共子序列即判为正确(空串也算合法答案)。