记录每个节点的答案的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;
}