← 返回题目列表

AtCoder · dp_f

F. 濒海战斗舰

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

给你字符串 s 和 t。 找到一个最长的字符串,它是两者的子序列 字符串的 s 和 t.

注释

A 子序列 一个字符串的 x 是删除零个或多个字符后得到的字符串 x 并连接其余字符而不改变顺序。

约束

  • s 和 t 是由小写英文字母组成的字符串。
  • 1 \leq |s|, |t| \leq 3000

输入

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

s
t

输出

打印一个最长的字符串,该字符串是两者的子序列 s 和 t。 如果有多个这样的字符串,则其中任何一个都将被接受。


示例输入 1

axyb
abyxb

示例输出 1

axb

答案是 axb or ayb;任何一个都会被接受。


示例输入 2

aa
xayaz

示例输出 2

aa

示例输入 3

a
z

示例输出 3


答案是 (空字符串)。


示例输入 4

abracadabra
avadakedavra

示例输出 4

aaadara