给定 $n$ 个字符串 $s_1, s_2, \cdots, s_n$，你要对每个字符串取一个非空前缀，然后按照某个顺序将这 $n$ 个前缀拼接起来，得到字符串 $S$。求字典序最小的 $S$。
第一行包含一个正整数 $n$ ($n \leq 50$)，表示字符串的个数。
接下来 $n$ 行，每行包含一个由大写字母 $\texttt A, \texttt C, \texttt G, \texttt T$ 构成的字符串 $s_i$ ($1 \leq \left| s_i \right| \leq 50$)。
输出一行，包含一个字符串，表示字典序最小的 $S$。
首先，为了避免下文的各种讨论，我们在每个字符串末尾加一个字典序极大的字符，比如 $\texttt U$。
这样做，一方面，它显然不影响答案 (因为我们怎么样都不可能将字符 $\texttt U$ 加入到最终的答案中)，另一方面，它也使每个串 $s_i$ 变为非循环串 (即 $s_i \neq s^k, k \geq 2$)，事实上，它变成了 borderless 的串。
那，具体该怎么取前缀并拼接呢？
我们从无限多个相同的串 $s$ 的情形着手考虑。
不妨设我们现在有无穷多个 $s$，那么最终拼成的答案显然也是一个无穷串 $t$。
而且，进一步可以证明，这个 $t$ 实际上也是一个周期串，即存在 $1 \leq k \leq \left| s \right|$，满是 $t = s \left[ 1 .. k \right]^\infty$。
(ps: 事实上，若 $t$ 不是周期串，由最小数原理考虑第一个非周期的位置，那么把前面的周期部分去掉，可以得到一个字典序更小的串，矛盾)
那具体 $k$ 的取值是多少呢？直接讨论似乎不太容易，我们还是要分析 $k$ 的性质。
首先，我们可以假设 $s \left[ 1 .. k \right]$ 不是循环串，否则我们令 $k$ 为它的最小周期。
一方面，对于 $k' < k$，$k'$ 不如 $k$ 优。这说明了什么？
$s \left[ 1 .. k' \right]^\infty > s \left[ 1 .. k \right]^\infty \Leftrightarrow s \left[ 1 .. k' \right]^\infty > s \left[ k' + 1 .. k \right] \cdot s \left[ 1 .. k \right]^\infty$。
首先，第一个结论是：$s \left[ 1 .. k \right]$ 是最大表示串，即 (在反向意义下) $s \left[ 1 .. k \right]$ 是 Lyndon 串。
(ps: 这里由于我们规定了 $s \left[ 1 .. k \right]$ 不循环，因此 Lyndon 串就是严格 Lyndon 串，且后缀最小与循环表示最小等价)
若 $s \left[ 1 .. k \right]$ 不是最大表示串，设 $s \left[ 1 .. k \right]$ 的 Lyndon 分解为 $s = u_1 \cdot u_2 \cdot \cdots \cdot u_l$，其中 $u_1 \leq u_2 \leq \cdots \leq u_l$，$l \geq 2$，且诸 "$\leq$" 中至少有一个是严格不等号 (因为 $s \left[ 1 .. k \right]$ 不是循环串，同时规定一个串的前缀大于本身)。
于是 $u_1^\infty < \left( u_1 \cdot u_2 \cdot \cdots \cdot u_l \right)^\infty = s^\infty$，矛盾。
于是，设 $s$ 的 Lyndon 分解为 $u_1 \cdot u_2 \cdot \cdots \cdot u_l \cdot \texttt U$，则 $s \left[ 1 .. k \right]$ 一定是 $u_1$ 或它的前缀。
下面证明第二个结论：$s \left[ 1 .. k \right] = u_1$。
若不成立，则设 $u_1 = s \left[ 1 .. K \right]$，最终答案为 $s \left[ 1 .. k \right]$，且 $k < K$。
设 $c$ 为最大的整数，满足 $s \left[ 1 .. K \right] = s \left[ 1 .. k \right]^c \cdot s \left[ c k + 1 .. K \right]$。由定义知，$c \geq 1$。
此时必有 $s \left[ 1 .. k \right] > s \left[ c k + 1 .. K \right]$，否则 $s \left[ c k + 1 .. K \right]$ 将会是更大的后缀，和最大表示串的定义矛盾。
于是 $s \left[ 1 .. k \right]^\infty = s \left[ 1 .. k \right]^c \cdot s \left[ 1 .. k \right]^\infty >t s \left[ 1 .. k \right] \cdot s \left[ c k + 1 .. K \right] \cdot s \left[ 1 .. K \right]^\infty$，矛盾。
综上，我们得到了：满足条件的 $s \left[ 1 .. k \right]$ 其实就是将 (末尾为 $\texttt U$ 的) 串 $s_i$ 进行 Lyndon 分解后的第一段。由 Lyndon 分解是线性的可知可以在线性时间内求出 $k$。
下面考虑有多个不同的串的情形。
根据上面的经验，我们将一个串 Lyndon 分解后的第一段称为这个串的核 (core)。
我们先考虑所有串的核两两不同的情况，和上面类似地，可以证明：最终的顺序一定是按照核 (的无穷循环) 的字典序递增的顺序。
(ps: 注意到这里的核都是 Lyndon 串，因此按照无穷循环排序等价于一般字典序加上 "前缀大于自身" 这一条件)
使用类似的思想，考虑交换两个串，容易证明将核小的串放在前面恒不比将核大的串放在前面劣。
那么，对于核相同的若干串，和第二部分的证明类似，我们在每个串的前缀取出尽可能多的 "核" (即找到尽可能大的 $c$ 使得 $s = s \left[ 1 .. k \right]^c \cdot s \left[ c k + 1 .. \right]$)，考虑后面这些 "尾巴"。
显然，这些尾巴我们至多要一个，因为尾巴大于核 (注意这个过程的实质就是 Lyndon 分解，而 Lyndon 分解式满足递增的)，如果我们要了俩尾巴，那么把前面一个尾巴切除后肯定更优。
那具体取那个尾巴呢？当然是字典序最小的尾巴啦 (如有相同任取一个)。不过还是要注意这里的字典序需要满足前缀大于自身。
同时，我们还可以把除了这个串之外的其它串的 "尾巴" 都 "切除" 掉，这也不影响答案。
确定完了顺序，最后我们就只需要确定长度了。
这就非常像字典序的贪心，或者 DP 了。
不妨设顺序就是 $s_1, s_2, \cdots, s_n$。
不难发现，无论 $s_1$ 取了多长的前缀，当它的长度固定时，$s_2 \sim s_n$ 一定取到它们所能取到的字典序最小的串 (最优子结构！)。
于是，我们只需要倒着加入这些串，每次统计出 $s_i, s_{i+1}, \cdots, s_n$ 所能达到的字典序最小的串，然后枚举 $s_{i-1}$ 的长度，逐个加入即可。
由于 $n$ 非常小，因此暴力实现就可以了，时间复杂度的上界为 $O \left( \left( \sum \left| s_i \right| \right)^2 \right)$。
当然，可以使用一些神秘(bì)技巧 (比如下面的代码) 来做到 $O \left( \sum \left| s_i \right| \right)$。
#include <bits/stdc++.h>
using std::string;
const int N = 3054;
struct data {
string pre, suf, pre2;
int cnt;
data () {}
data (string prefix, int count, string suffix) : pre(prefix), suf(suffix), pre2(prefix + '\x7f'), cnt(count) {}
inline bool operator < (const data &B) const {return pre2 < B.pre2 || (pre2 == B.pre2 && suf > B.suf);}
} r[54];
int n;
char s[N], *p = s + N - 2;
char h[N];
int find_first(int n, const char *s) {
int u = 1, v = 0;
for (; u <= n; s[u++] == s[v] ? ++v : v = 0)
if (s[u] > s[v]) return u - v;
abort();
}
int main() {
int i, j, d, u, v, L, Li; char *q;
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%s", s), L = strlen(s), s[L] = '\x7f', d = find_first(L, s);
for (u = d; !memcmp(s + u, s, d); u += d);
r[i] = data(string(s, s + d), u / d, string(s + u, s + (L + 1)));
}
std::sort(r, r + n);
for (i = 1; i < n; ++i) if (r[i - 1].pre == r[i].pre) r[i - 1].suf = "\x7f";
p[1] = '\x7f';
for (i = n - 1; i >= 0; --i) {
Li = find_first(s + (N - 1) - p, p);
for (q = h, j = 0; j < r[i].cnt; ++j) q += r[i].pre.copy(q, r[i].pre.size());
q += r[i].suf.copy(q, r[i].suf.size()), L = q - h;
for (d = u = 1, v = 0; u < L; ++u) {
if (h[u] > p[v]) {d = u - v; break;}
else (h[u] == p[v] && ++v != Li) || (v = 0);
}
memcpy(p -= d, h, d);
}
return puts(p), 0;
}
坑1：注意每个串都要取非空前缀，不要取漏了。
坑2：在每个串末尾加 $\texttt U$ 的另一个主要目的是方便前缀大于自身这种奇葩的比较需求。
坑3：注意并不是每个串的 "核" 会被完整地添加到答案中，"核" 仅仅是为了确定顺序。
比如，对于两个 $\texttt{CCAG}$，它们的核均为 $\texttt{CCA}$，但是答案显然是 $\texttt{CC}$，没有一个完整的核被加入 (但是当数量为 $+ \infty$ 个时就一定是核了，如上所证)。