2026 CSP-S 模拟卷（一）T3 词库检索

题目背景与题意

小 Z 有一个词库，里面装了 $n$ 个单词，每个单词只由小写英文字母组成。他会用 $q$ 个前缀来检索：对每个前缀，他想知道词库里有多少个单词以这个前缀开头。例如词库为 apple、app、apricot，前缀 ap 的答案是 3，前缀 app 的答案是 2（apple 与 app），前缀 ban 的答案是 0。

一个单词可能重复出现多次，重复出现要重复计数：如果词库里有两个完全相同的单词 app，那么前缀 app 的答案要算 2 个。

输入格式

第一行两个整数 $n, q$。

接下来 $n$ 行，每行一个仅含小写字母的非空字符串，表示一个单词。

接下来 $q$ 行，每行一个仅含小写字母的非空字符串，表示一次查询的前缀。

输出格式

共 $q$ 行，每行一个整数，依次回答每个前缀对应的单词个数。

样例输入

5 3
apple
app
apricot
banana
application
app
ap
ban

样例输出

3
4
1

样例解释

词库里五个单词是 apple、app、apricot、banana、application。

• 前缀 app：apple、app、application 三个匹配，答案是 3。
• 前缀 ap：apple、app、apricot、application 四个匹配，答案是 4。
• 前缀 ban：只有 banana 匹配，答案是 1。

数据范围与子任务

子任务	分值	约束	特殊性质
1	25	$n, q \le 200$，每个串长 $\le 20$	无
2	20	$n \le 200$	$q \le 10^5$
3		所有串长度之和 $\le 2000$
4	35	无	所有串长度之和 $\le 10^6$

对全部数据：$1 \le n \le 2\times 10^5$，$1 \le q \le 2\times 10^5$，输入中所有字符串（含查询）的长度之和不超过 $10^6$，字符串仅含小写字母且非空。

子任务采用捆绑测试：子任务内部的测试点必须全部通过才能拿到该子任务的全部分值，否则该子任务得 0 分。

时间限制 1 秒，空间限制 512 MB。