字典树
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define ull unsigned long long
#define endl '\n'
using namespace std;
const int N=1e6;
int ch[N+50][26],id,cnt[N+50],n,m;
string s;
void insert(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int x=s[i]-'a';
if(ch[p][x]==0)
{
ch[p][x]=++id;
}
p=ch[p][x];
}
cnt[p]++;
}
int query(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int x=s[i]-'a';
if(ch[p][x]==0)
{
return 0;
}
p=ch[p][x];
}
return cnt[p];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
while(n--)
{
cin>>s;
insert(s);
}
cin>>m;
while(m--)
{
cin>>s;
cout<<query(s)<<endl;
}
return 0;
}
Cpp
INFO