$\text{Description}$
给定一个字符串 $s[1\cdots n]$，定义字符串 $s_i$ 为 $s[1\cdots i-1]+s[i+1\cdots n]$，试为 $s_1,s_2,\cdots,s_n$ 排序。
$n\le 10^6$
$\text{Solution}$
一个朴素的想法是预处理所有串然后暴力排序，时间复杂度 $O(n^2\log n)$。
回顾字符串的排序：从前往后一位一位比较，若相同则继续比较，否则可以结束。
那么 $s_1,s_2,\cdots,s_n$ 的最大特点就是：重复字符多。
我们从具体情况入手（以下字符虽然表示上相同，但实际情况中可能不相同）：
首先我们从第一位开始比较，容易发现 $s_2,s_3,s_4,s_5$ 的第一位都为 $\texttt{!}$，故我们只需比较 $\texttt{!}$ 与 $\texttt{?}$，接下来分三类讨论。
$\texttt{!}=\texttt{?}$。此时可以消去所有串的第一位，我们将得到：
容易发现 $s_1$ 与 $s_2$ 相同，由于题目要求编号小的在前面，所以我们得到了 $s_1$ 的排名恰好在 $s_2$ 前。然后我们将 $s_1$ 略去，现在比较剩下的串时，就归约到规模更小而形式相同的情形了。
$\texttt{!}<\texttt{?}$。此时 $s_1$ 是当前的串中排名最末的串，随后我们将 $s_1$ 及 $\texttt{!}$ 略去，即可归约到规模更小而形式相同的情形了。
$\texttt{?}<\texttt{!}$。此时 $s_1$ 是当前的串中排名最前的串，随后就与上面的那个情形同理了。
于是可以逐步完成整个过程，其中第一种情况可以把前者和后者绑定在一起，当后者可以被塞入当前最前或最末时按照一定顺序一并塞入即可。
最后一个串只需让 $s[n]$ 和空气比较就行了，具体细节见代码。
$\text{Code}$
1 |
|