题目描述

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

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

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

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

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

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

每个答案占一行。

样例

输入样例：
3 2
ab
bc
abc
abc
efg

输出样例：
2
0

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;
typedef long long ll;
const int N = 1e6+10;
int son[N][26],cnt[N];
int idx=0;
char str[N];
void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int &s = son[p][str[i]-'a'];//这里引用，节省空间时间
        if(!s)
        {
            s=++idx;//对应的son值也更新
        }
        p=s;
    }
    cnt[p]++;
}
int search()
{
    int p=0,res=0;
    for(int i=0;str[i];i++)
    {
        int &s = son[p][str[i]-'a'];
        if(!s)break;
        p=s;
        res+=cnt[p];
    }
    return res;
}
int main()
{
    int n , m ;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str);
        insert();
    }
    while(m--)
    {
        scanf("%s",str);
       printf("%d\n", search());
    }
    return 0;
}