分数: 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