T467532 [2024迎新马拉松] 字典

给定一本字典。字典共包含 $N$ 个单词 $w_1, w_2, \ldots, w_N$。这些单词两两不同，并且全由小写字母组成。 现在有 $Q$ 个单词查找任务。每个任务会指定字母串 $s_{i1}$ 与 $s_{i2}$，并请你计算字典中有多少单词的前缀为 $s_{i1}$ 且后缀为 $s_{i2}$。

第一行包含两个整数 $N, Q$，表示字典大小、任务数量。 接下来 $N$ 行，每行一个小写字母串 $w_i$，描述字典中的单词。 最后 $Q$ 行，每行一个查找串 $s_i$，依次描述每一个单词查找任务。$s_i$ 中**恰好**包含一个星号 `*`。星号之前的部分表示指定的前缀 $s_{i1}$，之后的表示后缀 $s_{i2}$。

共 $Q$ 行，每行一个整数，依次表示相应查找任务的答案。

【样例解释#$1$】 字典中只有单词 `abcc`。所有查找任务均能发现这一单词： - `abc` 是该单词的前缀，`c` 是该单词的后缀； - `abc` 是该单词的前缀，`cc` 是该单词的后缀； - 空串是该单词的前缀，`cc` 是该单词的后缀。 【样例解释#$2$】 共有 $5$ 个单词，$3$ 个单词查找任务： - 任务 `*uwu` 能够查找到一个单词 `siyishuwu`； - 任务 `*` 能够查找到所有单词，共 $5$ 个； - 任务 `s*` 能够查找到两个单词 `siyishuwu`、`shaonianhu`。 【数据规模】 本题共有三个子任务，每个子任务捆绑计分： - 子任务一，占分 $15\%$，保证 $\sum |w_i|,\sum |s_i|\le 100$。 - 子任务二，占分 $30\%$，星号 `*` 只会在 $s_i$ 的开头或末尾。 - 子任务三，占分 $55\%$，无特殊约定。 对于全部测试数据，保证 $1 \le N, Q, |w_i|, |s_i| \le 10^6$，$1 \le \sum |w_i|, \sum |s_i| \le 10^6$。