题目描述

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

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

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

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

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

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

每个答案占一行。

样例

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

字典树

统计前缀个数,一想到字符串的前缀,我们就应该想到字典树,这个和字典一样的前缀树.

这道题目是字典树模板的略微改动,我们发现这道题目和一般字典树的查询不一样,字典树一般查询是看这个字符串是否出现,而这道题目这是统计这个字符串出现的次数.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=1e6+10;
char str[N];
int trie[N][26],n,m,i,j,t,End[N],tot=1;
void insert(char a[])
{
    int len=strlen(a),p=1;
    fir(i,0,len-1)
    {
        int ch=a[i]-'a';
        if (trie[p][ch]==0)
            trie[p][ch]=(++tot);
        p=trie[p][ch];
    }
    End[p]++;//统计个数
}
int Search(char a[])
{
    int len=strlen(a),p=1,ans=0;
    fir(i,0,len-1)//把这个字符串所有的前缀都找出来
    {
        p=trie[p][a[i]-'a'];
        if (p==0)
            return ans;
        ans+=End[p];
    }
    return ans;
}
int main()
{
    scanf("%d%d\n",&n,&t);
    fir(i,0,n-1)
    {
        scanf("%s\n",str);
        insert(str);
    }
    while(t--)
    {
        scanf("%s\n",str);
        printf("%d\n",Search(str));
    }
    return 0;
}