给定 $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$ 个时就一定是核了,如上所证)。