142. 前缀统计【trie】
统计 前缀 Trie 142
2023-09-11 14:15:52 时间
基础的trie树题
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int son[N][26],cnt[N],idx;
int n,m;
void insert(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int u=s[i]-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}
int query(string s)
{
int p=0,sum=0;
for(int i=0;i<s.size();i++)
{
int u=s[i]-'a';
if(!son[p][u]) return sum;
p=son[p][u];
sum+=cnt[p];
}
return sum;
}
int main(void)
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
string s; cin>>s;
insert(s);
}
for(int i=0;i<m;i++)
{
string s; cin>>s;
cout<<query(s)<<endl;
}
return 0;
}