YQWQ @ 2023-07-13 16:33:43
#include <bits/stdc++.h>
using namespace std;
const int Kmax=3e6,MAXN=75;
int T,n,m,t,now;
string s;
struct trieN{
int is_l;
int next[MAXN];
}trie[Kmax];
void fil(){
for(int i=0;i<=t;i++){
trie[i].is_l=0;
for(int j=0;j<MAXN;j++){
trie[i].next[j]=0;
}
}
}
void build(int p,int i){
trie[p].is_l++;
now=trie[p].next[s[i]-'0'];
if(!now) now=trie[p].next[s[i]-'0']=++t;
if(i<s.size()-1){
build(now,i+1);
}
}
void find(int p,int i){
// cout<<" "<<p<<" "<<i<<endl;
if(i==s.size()-1){
cout<<trie[p].is_l<<endl;
}else{
now=trie[p].next[s[i]-'0'];
if(!now) cout<<0<<endl;
else{
find(now,i+1);
}
}
}
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
cin>>T;
while(T--){
t=0;
cin>>n>>m;
for(int i=1;i<=n+m;i++){
cin>>s;
if(i<=n) build(0,0);
else find(0,0);
}
fil();
}
}
by henryyin @ 2023-07-28 22:21:45
我也是在这里被卡了...
将
trie[p].is_l++;
now=trie[p].next[s[i]-'0'];
两行调换位置,并且将
if(i==s.size()-1){
cout<<trie[p].is_l<<endl;
}
改为
if(i==s.size()){
cout<<trie[p].is_l<<endl;
}
就对了
相当于update时每次存的节点的size都是父节点的,所以query时变为
if(i==s.size())
问题在于当s.size()=1的时候的答案和s.size()=0是一样的,都返回的是 trie[0].is_l