字典树

#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;
}