A6973. 古老卷轴的修复

# 题目背景

考古学家在挖掘一座被遗忘的遗迹时，发现了两份残缺的羊皮卷副本。据考证，这两份副本 $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$。

## 数据范围与提示

对于 $100\%$ 的数据，满足 $1 \le |S|, |T| \le 1000$，且字符串仅由小写英文字母组成。

## 样例 1 解释
str1 = "abac" 是 "cabac" 的子序列（删去第一个 'c'）。
str2 = "cab" 是 "cabac" 的子序列（删去末尾的 "ac"）。
长度为 5，是所有可能方案中最短的。另一个合法的最短答案是 "cabac" 本身（此例只有这一个解，但在其他例子中可能有多个）。