102192: [AtCoder]ABC219 C - Neo-lexicographic Ordering
Description
Score : $300$ points
Problem Statement
Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.
The new alphabetical order is represented by a string $X$, which is a permutation of a, b, $\ldots$, z. The $i$-th character of $X$ $(1 \leq i \leq 26)$ would be the $i$-th smallest English lowercase letter in the new order.
The kingdom has $N$ citizens, whose names are $S_1, S_2, \dots, S_N$, where each $S_i$ $(1 \leq i \leq N)$ consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.
What is the lexicographical order?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings $S$ and $T$.
Below, let $S_i$ denote the $i$-th character of $S$. Also, if $S$ is lexicographically smaller than $T$, we will denote that fact as $S \lt T$; if $S$ is lexicographically larger than $T$, we will denote that fact as $S \gt T$.
- Let $L$ be the smaller of the lengths of $S$ and $T$. For each $i=1,2,\dots,L$, we check whether $S_i$ and $T_i$ are the same.
- If there is an $i$ such that $S_i \neq T_i$, let $j$ be the smallest such $i$. Then, we compare $S_j$ and $T_j$. If $S_j$ comes earlier than $T_j$ in alphabetical order, we determine that $S \lt T$ and quit; if $S_j$ comes later than $T_j$, we determine that $S \gt T$ and quit.
- If there is no $i$ such that $S_i \neq T_i$, we compare the lengths of $S$ and $T$. If $S$ is shorter than $T$, we determine that $S \lt T$ and quit; if $S$ is longer than $T$, we determine that $S \gt T$ and quit.
Constraints
- $X$ is a permutation of
a,b, $\ldots$,z. - $2 \leq N \leq 50000$
- $N$ is an integer.
- $1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)$
- $S_i$ consists of lowercase English letters. $(1 \leq i \leq N)$
- $S_i \neq S_j$ $(1 \leq i \lt j \leq N)$
Input
Input is given from Standard Input in the following format:
$X$ $N$ $S_1$ $S_2$ $\vdots$ $S_N$
Output
Print $N$ lines. The $i$-th line $(1 \leq i \leq N)$ should contain the $i$-th smallest name when the citizens' names are sorted according to the alphabetical order decided by Takahashi.
Sample Input 1
bacdefghijklmnopqrstuvwxzy 4 abx bzz bzy caa
Sample Output 1
bzz bzy abx caa
In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.
Sample Input 2
zyxwvutsrqponmlkjihgfedcba 5 a ab abc ac b
Sample Output 2
b a ac ab abc
Input
题意翻译
给定一个字符串 $x$，保证其长度为 $26$ 且由`a`到`z`的所有字母重新排列而成。当甲字符比乙字符在 $x$ 中先出现时，甲字符小于乙字符。 同时给出 $n$ 个字符串 $s_i$。请将 $s_i$ 按照新定义的字典序重新排序后输出。Output
问题描述
统治者AtCoder王国的Takahashi决定更改英语小写字母的字母顺序。
新的字母顺序由一个字符串$X$表示，它是a，b，$\ldots$，z的排列。$X$的第$i$个字符（$1 \leq i \leq 26$）是新顺序中第$i$小的英语小写字母。
该国有$N$位公民，其名字分别为$S_1$，$S_2$，$\ldots$，$S_N$，其中每个$S_i$ $(1 \leq i \leq N)$由英语小写字母组成。
按照Takahashi决定的字母顺序，对这些名字进行字典序排序。
什么是字典序？
简单来说，字典序就是字典中单词的排列顺序。更正式的定义如下，是用于确定不同字符串$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)$
输入
从标准输入获取输入，格式如下：
$X$ $N$ $S_1$ $S_2$ $\vdots$ $S_N$
输出
打印$N$行。第$i$行（$1 \leq i \leq N$）应该包含公民姓名按照Takahashi决定的字母顺序排序后的第$i$小的名字。
样例输入1
bacdefghijklmnopqrstuvwxzy 4 abx bzz bzy caa
样例输出1
bzz bzy abx caa
在Takahashi设置的新字母顺序中，b小于a，z小于y。因此，按字典序排序公民的姓名将按升序得到bzz，bzy，abx，caa。
样例输入2
zyxwvutsrqponmlkjihgfedcba 5 a ab abc ac b
样例输出2
b a ac ab abc