#AT1911. C - Neo-lexicographic Ordering
C - Neo-lexicographic Ordering
C - 字典序排序
得分: 300 分
问题描述
统治AtCoder王国的高桥决定改变英文字母的顺序。
新的字母顺序由一个字符串 $X$ 表示，它是 a, b, $\ldots$, z 的一个排列。$X$ 的第 $i$ 个字符 $(1 \leq i \leq 26)$ 是新顺序中第 $i$ 小的英文字母。
王国有 $N$ 个公民，他们的名字是 $S_1, S_2, \dots, S_N$，其中每个 $S_i$ $(1 \leq i \leq N)$ 由小写英文字母组成。
根据高桥决定的字母顺序将这些名字按字典顺序排序。
什么是字典顺序？
简单地说，字典顺序是单词在字典中的列出顺序。更正式地说，以下是确定不同字符串 $S$ 和 $T$ 的字典顺序的算法。
下面，令 $S_i$ 表示 $S$ 的第 $i$ 个字符。同时，如果 $S$ 字典顺序小于 $T$，我们将表示这个事实为 $S \lt T$；如果 $S$ 字典顺序大于 $T$，我们将表示这个事实为 $S \gt T$。
- 令 $L$ 为 $S$ 和 $T$ 长度中较小的那一个。对于每个 $i=1,2,\dots,L$，我们比较 $S_i$ 和 $T_i$ 是否相同。
- 如果存在 $i$ 满足 $S_i \neq T_i$，令 $j$ 为最小的这样的 $i$。然后，我们比较 $S_j$ 和 $T_j$。如果 $S_j$ 在字母顺序中位于 $T_j$ 前面，我们确定 $S \lt T$ 并停止；如果 $S_j$ 在字母顺序中位于 $T_j$ 后面，我们确定 $S \gt T$ 并停止。
- 如果不存在 $i$ 满足 $S_i \neq T_i$，我们比较 $S$ 和 $T$ 的长度。如果 $S$ 比 $T$ 短，我们确定 $S \lt T$ 并停止；如果 $S$ 比 $T$ 长，我们确定 $S \gt T$ 并停止。
约束
- $X$ 是
a,b, $\ldots$,z的一个排列。 - $2 \leq N \leq 50000$
- $N$ 是一个整数。
- $1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)$
- $S_i$ 由小写英文字母组成。$(1 \leq i \leq N)$
- $S_i \neq S_j$ $(1 \leq i \lt j \leq N)$
输入
输入从标准输入中按以下格式给出:
输出
按顺序打印 $N$ 行。第 $i$ 行 $(1 \leq i \leq N)$ 的内容应该是按高桥决定的字母顺序排序时第 $i$ 小的名字。
bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa
bzz
bzy
abx
caa
在高桥设定的新字母顺序中， b 比 a 小，而 z 比 y 小。因此，按字典顺序对公民的名字进行排序将得到 bzz, bzy, abx, caa。
zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b
b
a
ac
ab
abc