【最优队名】

题目描述

ACM/ICPC 比赛按照解题数量给参赛比赛的队伍排序。当然,一场比赛中总会有几支队伍解出了相同数量的题目。ACM/ICPC 还有大量规则,比如罚时,可以给解决了相同数量题目的队伍排序。但是有时候,还是避免不了邮两支队伍在经过各个规则之后,依然有相同的排名。这时,我们就只能采用“字典序”给他们定名次了。

ACM/ICPC 各场比赛的规则总会有些细微的区别,大多数比赛会把字典序较小的队伍排在前面,而有些比赛却会将字典序较大的队伍排在前面。更加奇怪的赛区会重新定义一遍字母的顺序,比如规定‘b’才是排在最前面的字符。这样 26 个字母按从小到大的顺序就成了“bacdefghijklmnopqrstuvwxyz”,从而“ba”就将排在“ab”之前。注意,“b”应该排在“ba”之前。即,若 s 是 t 的前缀,那么 s 排在 t 之前。

现在我想好了很多个喜欢的队名。也知道每场比赛按“字典序”排序的规则。对于每一场比赛,请帮我挑一个在知道这场比赛的规则下,最占优势的名字是哪一个?

输入格式

第一行为两个整数 n,m,依次代表备选的队名个数和比赛的数量。
接下来 n 行,每行一个仅包含 26 个小写字符的字符串,长度不超过 30。
接下来 m 行,每行 26 个字符,为一个 26 个小写字母的排列,代表了这场比赛重新定义的字母顺序。越先出现的字母则越优先排在前面。

输出格式

输出 m 行字符串,依次是每场比赛最占优势的队名。

样例数据 1

输入

3 2
abc
bac
cab
abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba

输出

abc
cab

备注

【数据范围】
对于 30% 的数据有:N≤2000,M≤2000。
对于 100% 的数据有:N≤10000,M≤100000。

考场上想不出来这道题简直蠢哭……就是把N个字符串建Trie树,然后对M个字典序每个按顺序在Trie树上找有没有这个点,注意题目说是前缀就排在前面,所以如果找到结点是终点的话就break了,注意break的位置,因为找的是一个点的儿子,所以now要先更新后再看这个节点是不是终点。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*