C题，但是是线性

Concatenation

https://ac.nowcoder.com/acm/contest/33188/C

C题，但是是线性，但是是小白向题解

前置知识：字典树、DFS序

预期读者：牛牛多校能打到前400的都可以读（？

主要内容

尽管sort可过，但本题解主要介绍如何以 $O(\Sigma|s_i |)$ 的时间通过此题。本题解和PDF题解做法基本一致，主要是PDF题解写的不是很好懂，希望这个比PDF题解好懂（希望）。

首先

这里将trie上对应某输入串结尾的点称作红点，如输入串中有123，则该3对应的trie节点为红点。

下文提到dfs时，是指按照0、1、2、3、4的顺序来dfs。

回忆一下，本题的目标是得到 $n$ 个串的排序结果，之中排序的规则为：对于两个串 $a, b$ ，若 $a + b < b + a$ 则认为 $a$ “小于” $b$ 。（一个和这篇题解没什么关系的思考题：为何这样定义的大小关系是偏序的？）

其次

结论一：若两个红点 $x$ 和 $y$ 在树上不存在父子关系（即，“ $x$ 不在根到 $y$ 的路径上”且“ $y$ 不在根到 $x$ 的路径上”），则两者中DFS序小的就是排序结果里小的。

这个可以根据字典树性质和DFS序定义直接得到。

结论二：考虑这样一个问题：给定字符串 $S$ ，求出有哪些 $i$ 使得 $S [1 : i]$ 满足 $S [1 : i] + S < S + S [1 : i]$ ，之中 $S [1 : i]$ 表示 $S$ 长为 $i$ 的前缀。则该问题可以通过 $Z$ 函数（扩展KMP）在 $O (∣ S ∣)$ 复杂度内求解。（一开始不会做这个，被 jls 教育了orz）

具体解法考虑下图：

alt

图中，我们想 $O (1)$ 的比较出上面的串串（ $S + S [1 : i]$ ）和下面的串串（ $S [1 : i] + S$ ）的大小。图中x和y表示箭头所指位置在 $S$ 串中的下标。我们可以 $O (∣ S ∣)$ 求出串串的 $Z$ 函数数组 $z$ ， $∣ S ∣$ 表示串长。

众所周知，比较两个字符串的大小，其实就是找到两个字符串第一个不相等的位置，那么我们来看看图。

首先，蓝色圈一部分肯定完全相等。

若不相等位置出现在蓝色圈二部分，则可以通过 $Z$ 函数 $z [x]$ 的值来确定其位置。具体原因可以通过盯着蓝色圈二所框出的两串部分来领悟。

若不相等位置出现在蓝色圈三部分，则可以通过 $Z$ 函数 $z [y]$ 的值来确定其位置。具体原因可以通过盯着蓝色圈三所框出的两串部分来领悟。

因此，可以 $O (1)$ 对于每一个 $i$ 做判断，也就可以 $O (∣ S ∣)$ 求出所有的。

于是

最终的做法如下：

我们dfs这颗trie树，并通过一个vector来记录排序结果（题解用的链表，没什么区别），该vector中总存有当前所有串排好序的结果（也就是说当我们dfs到第 $k$ 个红点时，vector里存有前 $k - 1$ 个红点对应的串排好序的结果）

那么当我们dfs到第 $k$ 个红点 $x$ 的时候，vector里的 $k - 1$ 个红点可以分成两类：不在根到 $x$ 的路径上的红点和在根到 $x$ 的路径上的红点。

按照之前的结论，前一类所对应的字符串一定小于 $x$ 所对应的字符串，且当前vector里的 $k - 1$ 个点一定是形如：【若干个第一类红点、若干个第二类红点】这样的，所以我们只关心把当前 $x$ 插到第二类红点的哪个位置，可以使得排序正确。

于是，我们对 $x$ 节点所对应的串求出上面 $Z$ 函数那个问题的答案，复杂度 $O (∣ S ∣)$ ，然后据此来判断 $x$ 要插到vector尾部的哪里就可以了，这里的插入操作可以通过直接在vector尾部暴力插来完成，因为vector尾部的第二类红点也是 $O (∣ S ∣)$ 的数量级（由第二类红点的定义）。所以把 $x$ 插到vector里正确的位置所需的总时间是 $O (∣ S ∣)$ 。