AT_abc219_c [ABC219C] Neo-lexicographic Ordering

题目描述

AtCoder 王国的统治者高桥君决定更改英文字母的字母顺序。

新的字母顺序由将 a、b、$\ldots$、z 重新排列得到的字符串 $X$ 表示。$X$ 的第 $i$ 个字符（$1 \leq i \leq 26$）表示在新的顺序中第 $i$ 小的英文字母。

AtCoder 王国有 $N$ 位国民，每位国民的名字分别为 $S_1, S_2, \dots, S_N$。其中，$S_i$（$1 \leq i \leq N$）由小写英文字母组成。 请根据高桥君制定的新字母顺序，对这些名字按字典序进行排序。

什么是字典序？字典序简单来说就是“单词在字典中出现的顺序”。更严格地说，判断由小写英文字母组成的不同字符串 $S$、$T$ 的大小关系的算法如下：

下面用 $S_i$ 表示 $S$ 的第 $i$ 个字符。当 $S$ 在字典序上小于 $T$ 时记作 $S < T$，大于时记作 $S > T$。

1. 设 $L$ 为 $S$ 和 $T$ 中较短的字符串的长度。对于 $i=1,2,\dots,L$，依次比较 $S_i$ 和 $T_i$ 是否相同。
2. 如果存在 $S_i \neq T_i$ 的 $i$，则取最小的这样的 $i$，记为 $j$。比较 $S_j$ 和 $T_j$，若 $S_j$ 在字母顺序上小于 $T_j$，则 $S < T$，否则 $S > T$，算法结束。
3. 如果不存在 $S_i \neq T_i$ 的 $i$，则比较 $S$ 和 $T$ 的长度，若 $S$ 比 $T$ 短，则 $S < T$，否则 $S > T$，算法结束。

输入格式

输入按以下格式从标准输入读入。

$X$
$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出 $N$ 行。第 $i$ 行输出按高桥君指定的新字母顺序排序后，第 $i$ 小的国民名字。

输入输出样例 #1

输入 #1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

输出 #1

bzz
bzy
abx
caa

输入输出样例 #2

输入 #2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

输出 #2

b
a
ac
ab
abc

说明/提示

限制条件

• $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 < j \leq N$）

样例解释 1

在高桥君新设定的字母顺序中，b 比 a 小，z 比 y 小。因此，按字典序排序后，国民的名字依次为 bzz、bzy、abx、caa。

由 ChatGPT 4.1 翻译