← 返回题单
题单练习 双序列型DP入门
← 上一题 下一题 →

A6973 | 古老卷轴的修复

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

题目背景



考古学家在挖掘一座被遗忘的遗迹时，发现了两份残缺的羊皮卷副本。据考证，这两份副本 $S$ 和 $T$ 都抄录自同一份神圣的原始卷轴 $U$。由于年代久远，副本 $S$ 和 $T$ 中都有不同程度的字符丢失，但保留下来的字符顺序与原始卷轴 $U$ 一致。换句话说，$S$ 和 $T$ 都是 $U$ 的子序列。

为了尽可能还原历史真相，考古学家认为原始卷轴 $U$ 的长度应该尽可能短。请你帮助考古学家重建这份原始卷轴。

题目描述



给定两个由小写英文字母组成的字符串 $S$ 和 $T$，请你构造一个字符串 $U$，使得：

1. $S$ 是 $U$ 的子序列。
2. $T$ 是 $U$ 的子序列。
3. $U$ 的长度 $|U|$ 是满足上述条件中最小的。

如果存在多个满足条件的字符串 $U$，输出任意一个即可。

*注意：若可以通过从字符串 $A$ 中删除若干个（也可以不删除）字符得到字符串 $B$，则称 $B$ 是 $A$ 的子序列。*

输入格式

输入包含两行。
第一行包含一个字符串 $S$。
第二行包含一个字符串 $T$。

输出格式

输出一行，包含一个字符串，即复原后的原始卷轴 $U$。

输入输出样例

输入 #1
abac
cab
输出 #1
cabac
输入 #2
aaaaaaaa
aaaaaaaa
输出 #2
aaaaaaaa
C++ 编辑器
输入
输出