题目描述
给定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
字典树
1. 用s1-sn构建字典树,在每一个Si结尾的节点打上标记cnt[p],记录Si出现的次数
2.与模板不同的是,这里的查询是枚举T的第i个字母作为T的前缀的结尾,在查询的时候累计ans,记录截止到T串第i个字母
时其对应在字典树中的前缀;
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int son[N][26],idx=0;
int cnt[N];
char s[N],t[N];
void insert(char* str)
{
int p=0;
for(int i=0;str[i];i++)
{
int j=str[i]-'a';
if(!son[p][j]) son[p][j]=++idx;
p=son[p][j];
}
cnt[p]++;
}
int query(char* str)
{
int p=0,ans=0;
for(int i=0;str[i];i++)
{
int j=str[i]-'a';
if(!son[p][j]) return ans;
p=son[p][j];
ans+=cnt[p];
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
scanf("%s",s);
insert(s);
}
for(int i=0;i<m;i++)
{
scanf("%s",t);
cout<<query(t)<<endl;
}
return 0;
}