← 返回题目列表

Codeforces · 1070/H

H. BerOS 文件建议

中文机器翻译题面 查看原题

Polycarp 正在开发一种名为 BerOS 的新操作系统。他请求您帮助实施文件建议功能。

硬盘上有$$$n$$$个文件,它们的名称是$$$f_1、f_2、\dots、f_n$$$。任何文件名都包含 $$$1$$$ 和 $$$8$$$ 之间的字符(含这两个字符)。所有文件名都是唯一的。

文件建议功能处理查询,每个查询都由字符串 $$$s$$$ 表示。对于每个查询 $$$s$$$,它应该计算包含 $$$s$$$ 作为子字符串的文件数量(即文件名中的某些连续字符段等于 $$$s$$$),并建议任何此类文件名。

例如,如果文件名是“read.me”、“hosts”、“ops”和“beros.18”,并且查询是“os”,则匹配的文件数为$$$2$$$(两个文件名包含“os”作为子字符串),建议的文件名可以是“hosts”或“beros.18”。

输入

输入的第一行包含整数 $$$n$$$ ($$$1 \le n \le 10000$$$) — 文件总数。

以下 $$$n$$$ 行包含文件名,每行一个。第 $$$i$$$ 行包含 $$$f_i$$$ — 第 $$$i$$$ 文件的名称。每个文件名包含 $$$1$$$ 和 $$$8$$$ 之间的字符(含)。文件名仅包含小写拉丁字母、数字和点字符(“.”)。任何有效字符序列都可以是文件名(例如,在 BerOS 中“.”、“..”和“...”是有效文件名)。所有文件名都是唯一的。

以下行包含整数 $$$q$$$ ($$$1 \le q \le 50000$$$) — 查询总数。

以下 $$$q$$$ 行包含查询 $$$s_1, s_2, \dots, s_q$$$,每行一个。每个 $$$s_j$$$ 的长度在 $$$1$$$ 和 $$$8$$$ 字符之间(含)。它仅包含小写拉丁字母、数字和点字符 ('.')。

输出

打印 $$$q$$$ 行,每个查询一行。第 $$$j$$$ 行应包含第 $$$j$$$ 查询的响应 — 两个值 $$$c_j$$$ 和 $$$t_j$$$,其中

- $$$c_j$$$ 是第 $$$j$$$ 查询的匹配文件数,
- $$$t_j$$$ 是与第 $$$j$$$ 个查询匹配的任何文件的名称。如果没有这样的文件,则打印单个字符“-”。如果有多个匹配的文件,则打印其中一个。

示例

输入 #1

4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st

输出 #1

1 contests
2 .test
1 test.
1 .test
0 -
4 test.