#G. 最长公共子序列LCS

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个字符串 $s$ 和一个字符串 $t$ ，输出 $s$ 和 $t$ 的最长公共子序列。

字符串 $x$ 的子序列是通过从 $x$ 中移除零个或多个字符，并按原有顺序连接剩余字符而得到的字符串。

两行，第一行输入 $s$ ，第二行输入 $t$ 。

输出 $s$ 和 $t$ 的最长公共子序列。如果有多种答案，输出任何一个都可以。

axyb
abyxb

axb

aa
xayaz

aa

a
z

abracadabra
avadakedavra

aaadara

数据保证 $s$ 和 $t$ 仅含英文小写字母，并且 $s$ 和 $t$ 的长度小于等于3000。