102192: [AtCoder]ABC219 C - Neo-lexicographic Ordering

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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$.

  1. 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.
  2. 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.
  3. 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

得分:300分

问题描述

统治者AtCoder王国的Takahashi决定更改英语小写字母的字母顺序。

新的字母顺序由一个字符串$X$表示,它是ab,$\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$表示。

  1. 让$L$为$S$和$T$长度的较小值。对于每个$i=1,2,\dots,L$,我们检查$S_i$和$T_i$是否相同。
  2. 如果存在一个$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$并退出。
  3. 如果没有$i$使得$S_i \neq T_i$,我们比较$S$和$T$的长度。如果$S$比$T$短,我们确定$S \lt T$并退出;如果$S$比$T$长,我们确定$S \gt T$并退出。

限制条件

  • $X$是ab,$\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小于az小于y。因此,按字典序排序公民的姓名将按升序得到bzzbzyabxcaa


样例输入2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

样例输出2

b
a
ac
ab
abc

加入题单

上一题 下一题 算法标签: