金丝猴人(如果你TLE ON #5
查看原帖
金丝猴人(如果你TLE ON #5
983702
lrj3247楼主2025/1/31 18:41

记录每个节点的答案的sum数组清空不能用memset,直接for循环 示例 TLE code:

#include <bits/stdc++.h>
using namespace std;
unordered_map <char,int> mp;
const int N = 3e6+15;
int sum[N],tr[N][62],tot,n,q;
void Insert(string &s){
	int len = s.size() , p = 1;
	for(int i = 0 ; i<len ; i++){
		int ch = mp[s[i]];
		if(tr[p][ch]==0)
		tr[p][ch]=++tot;
		p=tr[p][ch];
		sum[p]++;
	}
	return ;
}
int Query(string &s){
	int len = s.size() , p = 1;
	for(int i = 0 ; i<len ; i++){
		int ch = mp[s[i]];
		p=tr[p][ch];
		if(p==0){
			return 0;
		}
	}
	return sum[p];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int idx = 0;
	for(char i = '0' ; i<='9' ; i++) mp[i]=idx++;
	for(char i = 'A' ; i<='Z' ; i++) mp[i]=idx++;
	for(char i = 'a' ; i<='z' ; i++) mp[i]=idx++;
	int T;
	cin>>T;
	while(T--){
		memset(sum,0,sizeof(sum));
		for(int i = 1 ; i<=tot ; i++){
			for(int j = 0 ; j<=61 ; j++){
				tr[i][j]=0;
			}
		}
		tot=1;
		int n,q;
		cin>>n>>q;
		for(int i = 1 ; i<=n ; i++){
			string s;
			cin>>s;
			Insert(s);
		}
		for(int i = 1 ; i<=q ; i++){
			string s;
			cin>>s;
			cout<<Query(s)<<"\n";
		}
	}
	return 0;
}

AC code:

#include <bits/stdc++.h>
using namespace std;
unordered_map <char,int> mp;
const int N = 3e6+15;
int sum[N],tr[N][62],tot,n,q;
void Insert(string &s){
	int len = s.size() , p = 1;
	for(int i = 0 ; i<len ; i++){
		int ch = mp[s[i]];
		if(tr[p][ch]==0)
		tr[p][ch]=++tot;
		p=tr[p][ch];
		sum[p]++;
	}
	return ;
}
int Query(string &s){
	int len = s.size() , p = 1;
	for(int i = 0 ; i<len ; i++){
		int ch = mp[s[i]];
		p=tr[p][ch];
		if(p==0){
			return 0;
		}
	}
	return sum[p];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int idx = 0;
	for(char i = '0' ; i<='9' ; i++) mp[i]=idx++;
	for(char i = 'A' ; i<='Z' ; i++) mp[i]=idx++;
	for(char i = 'a' ; i<='z' ; i++) mp[i]=idx++;
	int T;
	cin>>T;
	while(T--){
		for(int i = 1 ; i<=tot ; i++){
			sum[i]=0;
			for(int j = 0 ; j<=61 ; j++){
				tr[i][j]=0;
			}
		}
		tot=1;
		int n,q;
		cin>>n>>q;
		for(int i = 1 ; i<=n ; i++){
			string s;
			cin>>s;
			Insert(s);
		}
		for(int i = 1 ; i<=q ; i++){
			string s;
			cin>>s;
			cout<<Query(s)<<"\n";
		}
	}
	return 0;
}
2025/1/31 18:41
加载中...