字典树36分求调
查看原帖
字典树36分求调
542879
_HCl_楼主2023/10/20 19:13

萌新刚学OI,请各位大佬帮忙看一下,低级错误请见谅

#include<bits/stdc++.h>
using namespace std;
int n,q;
int t[3000001][70],cnt[3000001],tot;
int getn(char ch){
	if('a'<=ch&&ch<='z')return ch-'a';
	if('A'<=ch&&ch<='Z')return ch-'a'+26;
	if('0'<=ch&&ch<='9')return ch-'0'+52;
}
void ins(string s){
	int p=0;
	for(int i=0;i<s.length();++i){
		int ch=getn(s[i]);
		if(!t[p][ch])t[p][ch]=++tot;
		p=t[p][ch];
		cnt[p]++;
	}
}
int que(string s){
	int p=0;
	for(int i=0;i<s.length();++i){
		int ch=getn(s[i]);
		if(!t[p][ch])return 0;
		p=t[p][ch];
	}
	return cnt[p];
}
void work(){
	for(int i=0;i<=tot;++i)for(int j=0;j<70;++j)t[i][j]=0;
	for(int i=0;i<=tot;++i)cnt[i]=0;
	tot=0;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		string s;
		cin>>s;
		ins(s);
	}
	for(int i=1;i<=q;++i){
		string t;
		cin>>t;
		cout<<que(t)<<"\n";
	}
}
int main(){
	int T;
	cin>>T;
	while(T--)work();
 } 
2023/10/20 19:13
加载中...