P8306 【模板】字典树

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=3e6+10;
int t;
int tr[N][62],idx,cnt[N];int get_id(char c)
{if(c>='a'&&c<='z') return c-'a';else if(c>='A'&&c<='Z') return c-'A'+26;else return c-'0'+52;
}void solve()
{int n,q;cin>>n>>q;for(int i=0;i<=idx;i++){for(int j=0;j<=61;j++){tr[i][j]=0;}cnt[i]=0;}idx=0;while(n--){string s;cin>>s;int p=0;for(char c:s ){int u=get_id(c);if(!tr[p][u]) tr[p][u]=++idx;p=tr[p][u];cnt[p]++;}}while(q--){string s;cin>>s;bool found=true;int p=0;for(char c:s ){int u=get_id(c);if(!tr[p][u]) {found=false;break;}p=tr[p][u];}cout<<(found ? cnt[p] : 0)<<"\n";}}int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>t;while(t--){solve();}return 0;
}