#M. [算法竞赛进阶指南]前缀统计

传统题

2000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定N个字符串S1,S2...SN，接下来进行M次询问，每次询问给定一个字符串T，求S1～SN中有多少个字符串是T的前缀。输入字符串的总长度不超过10^6^，仅包含小写字母。

字符串 S1（不妨假设长度为 n）被称为字符串 S2 的前缀，当且仅当：S2 的长度不小于 n，且 S1 与 S2 前 n 个字符组组成的字符串完全相同。

第一行两个整数N，M。接下来N行每行一个字符串Si。接下来M行每行一个字符串表示询问。

对于每个询问，输出一个整数表示答案

3 2
ab
bc
abc
abc
efg

2
0

Trie