P12773 [POI 2018/2019 R1] 马虎 Nonchalance

翻译来自于 [LibreOJ](https://loj.ac/p/4919)。

**题目译自 [XXVI Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi26-1/dashboard/) [Niedbałość](https://sio2.mimuw.edu.pl/c/oi26-1/p/nie/)** Bajtazar 先生是 Bajtocji 第 $2^{8}-1$ 高中的生物老师。他给 Bajtek 和同学们布置了一道遗传学作业：找出两个基因型之间的最大亲缘关系。也就是说，你得找到这两个基因型中都包含的最长氨基酸序列（不一定连续）。Bajtek 他们很清楚，这任务烦琐得要命，更别提懒惰的 Bajtazar 先生居然会花时间检查。他们从学长那儿听说，这位老师检查作业很马虎——他只看你给的序列能不能在某处再加一个氨基酸，还保持是两个基因型的子序列。如果加不进去，你就能拿满分。 假设基因型是只由字母 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$、$\texttt{T}$ 组成的序列。设 $S = (s_{1}, \ldots, s_{n})$ 和 $T = (t_{1}, \ldots, t_{m})$ 是给定的两个基因型，长度分别为 $n$ 和 $m$。要拿满分，你需要给出一个序列 $W = (w_{1}, \ldots, w_{k})$，它既是 $S$ 的子序列，也是 $T$ 的子序列，而且不存在任何长度为 $k+1$ 的序列 $W^{\prime}$，包含 $W$ 作为子序列，同时还是 $S$ 和 $T$ 的子序列。 请你帮 Bajtek 和他的小伙伴们拿到最高分。

输入第一行是一个长度为 $n$ 的基因型，用大写字母 $\texttt{A}$、$\texttt{T}$、$\texttt{C}$、$\texttt{G}$ 表示。 第二行是另一个长度为 $m$ 的基因型，格式相同。

输出一行，用 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$、$\texttt{T}$ 字母组成一个**不可扩展**的序列，作为输入中两个基因型的亲缘证据。如果有多个正确答案，你的程序可以输出任意一个。 保证答案始终存在且非空。

**样例 1 解释** `ATA` 和 `G` 也是合法的输出。 **附加样例** 1. $n=m=7$，基因型只有字母 $\texttt{A}$ 和 $\texttt{T}$； 2. $n=100, m=10000$，第一个基因型是第二个的子序列； 3. $n=m=1000000$，第一个基因型的氨基酸按字母顺序排列。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n, m \leq 12$ | $10$ | | $2$ | $n, m \leq 100$ | $10$ | | $3$ | $n, m \leq 1000$ | $10$ | | $4$ | $n, m \leq 50000$ | $20$ | | $5$ | $n, m \leq 1000000$，基因型仅包含 $\texttt{A}$ 和 $\texttt{T}$ | $20$ | | $6$ | $n, m \leq 1000000$ | $30$ |