← 返回题目列表

AtCoder · awc0057_b

B. 图书馆图书搜索

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

分数: 333 分

问题陈述

Takahashi 正在为图书馆开发图书搜索系统。图书馆有 N 书架,以及 i第一个书架(1 \leq i \leq N) 包含 K_i 书籍。的标题 j- 第本书 i第一个书架表示为 S_{i,j}。所有标题都是仅由小写英文字母组成的字符串。

在此搜索系统中,当用户输入字符串作为搜索查询时,系统会查找包含与该查询相关的书籍的书架。由于用户通常不记得书的确切书名,因此他们可能会按顺序(不一定是连续的)从书名中挑选一些字符并将其输入作为搜索。因此,本系统采用搜索方式 子序列.

这里是一个字符串 字符串的 T 是 子序列 一个字符串的 S if T 可以通过删除获得 0 或更多字符 S (不改变剩余字符的顺序)。例如, ace 是以下序列的子序列 abcde,但是 aec 不是以下的子序列 abcde.

的 i第一个书架 点击 查询字符串 T if T 是至少以下之一的子序列 S_{i,1}, S_{i,2}, \ldots, S_{i,K_i}。换句话说,该书架上至少存在一本书,其书名包含 T 作为子序列。

你被给予 Q 搜索查询。让 T_j 是字符串 j-第一个查询。对于每个查询,查找命中该查询的书架数量 T_j.

约束

  • 1 \leq N \leq 100
  • 1 \leq K_i \leq 5000
  • 1 \leq \displaystyle\sum_{i=1}^{N} K_i \leq 5000
  • 每个标题的长度 S_{i,j} 介于 1 和 1000,包括
  • \displaystyle\sum_{i=1}^{N}\sum_{j=1}^{K_i} |S_{i,j}| \leq 10^5
  • 1 \leq Q \leq 200
  • 每个查询的长度 T_j 介于 1 和 1000,包括
  • \displaystyle\sum_{j=1}^{Q} |T_j| \leq 10^5
  • S_{i,j} 和 T_j 是仅由小写英文字母组成的字符串

在这里, |X| 表示字符串的长度 X.


输入

N
K_1 S_{1,1} S_{1,2} \ldots S_{1,K_1}
K_2 S_{2,1} S_{2,2} \ldots S_{2,K_2}
\vdots
K_N S_{N,1} S_{N,2} \ldots S_{N,K_N}
Q
T_1
T_2
\vdots
T_Q
  • 第一行包含一个整数 N,书架数量。
  • 从第 2 行到 (N+1)第行, (i+1)- 第行 (1 \leq i \leq N) 包含书籍数量 K_i 上 i- 第一个书架,后跟标题 S_{i,1}, S_{i,2}, \ldots, S_{i,K_i},用空格分隔。
  • 的 (N+2)- 第行包含一个整数 Q,搜索查询数。
  • 从 (N+3)第 行 (N+Q+2)第行,对应的行 j第一个查询 (1 \leq j \leq Q) 包含搜索查询字符串 T_j.

输出

输出 Q 行。的 j- 第行 (1 \leq j \leq Q) 应包含命中查询的书架数量 T_j.


示例输入 1

2
2 algorithm data
2 string graph
3
ag
ri
zz

示例输出 1

1
2
0

示例输入 2

3
1 programming
2 problem process
2 apple application
4
po
pin
pp
rm

示例输出 2

3
2
1
2

示例输入 3

5
3 binary search tree
2 dynamic programming
1 graph
2 stack queue
3 linked list array
5
ar
ra
i
zzz
ee

示例输出 3

2
3
3
0
2