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

前置知识：字典树、DFS序

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

主要内容

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

首先

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

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

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

其次

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

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

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

具体解法考虑下图：

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

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

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

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

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

因此，可以$O(1)O(1)$对于每一个$ii$做判断，也就可以$O(\mathrm{\mid }S\mathrm{\mid })O(|S|)$求出所有的。

于是

最终的做法如下：

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

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

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

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

最后

dfs整颗trie树的时间是$O(\mathrm{\Sigma }\mathrm{\mid }{s}_i\mathrm{\mid })O(\backslash Sigma|s\_i\; |)$，对于每个红点找到他插入的位置所需时间也是$O(\mathrm{\Sigma }\mathrm{\mid }{s}_i\mathrm{\mid })O(\backslash Sigma|s\_i\; |)$，因此总复杂度$O(\mathrm{\Sigma }\mathrm{\mid }{s}_i\mathrm{\mid })O(\backslash Sigma|s\_i\; |)$。

好！

代码

对不起上面都是我口胡的，其实我没有买今年多校，所以无代码。如果有人照着上面写发现炸了，那概不负责捏。