原题链接

给定 N 个字符串 S1,S2…SN，接下来进行 M 次询问，每次询问给定一个字符串 T，求 S1∼SN 中有多少个字符串是 T 的前缀。

输入字符串的总长度不超过 10^6，仅包含小写字母。

输入格式

第一行输入两个整数 N，M。

接下来 N 行每行输入一个字符串 Si。

接下来 M 行每行一个字符串 T 用以询问。

输出格式

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

每个答案占一行。

输入样例：

3 2
ab
bc
abc
abc
efg

输出样例：

2
0

 解法：trie(字典树)

数组实现字典树：：由于输入全是小写字母，我们可以定义trie[N][26]表示trie树，表示有N个大小为26的一维数组

tot表示最后一个被用过的行，为了减少空间浪费，每次需要开辟新的空间，就开辟tot下一个行所在空间；

next表示某一个字符其下一个字符所在行数；

trie[i][j]存放的值是它的字符串中下一个字符所在的行数，i表示当前所在行数，j表示列数，即字母的值(数字)；

例如：输入ab，bc，abc：tot=0，

ab：next=0，trie[0][0]=1，表示下一个字符所在行(next)为1，trie[1][1]=2，表示下一个字符所在行(next)为2，tot=2；

bc：next=0，trie[0][1]=3，由于1，2行已经被用过，开辟新的空间只能用第3行，trie[3][2]=4，表示下一个字符所在行(next)为4；

abc：next=0，trie[0][0]=1,next=1,trie[1][1]=2,next=2,trie[2][2]=5(++tot)；

我们采取的策略是插入时给最后一个字符的下一个字符('\0')所在的行表示的cnt数组中+1，

cnt[i]表示以字符串的最后一个字符位置(trie[i][j])代表的值(下一个'\0'字符所在位置) 结尾的字符串数量，cnt[2]=1，cnt[4]=1，cnt[5]=1；

查找前缀时，数量=该路径上以某一行结尾的字符串数量和；

例：查询abc前缀字符串数量：a字符所在位置trie[0][0]，其代表值为1，res+=cnt[1]；

b所在位置trie[1][1]，其代表的值为2，res+=cnt[2]；

c所在位置trie[2][2]，其代表值为5，res+=cnt[5]；

所以res=2；