prolu @ 2024-04-17 13:48:01
#include<bits/stdc++.h>
using namespace std;
char ss[2500];
int ott=0,id;
int tied[3000000][80],sum[3000000];
void insert(){
int root=0;
int len=strlen(ss);
for(int i=0;i<len;i++){
id=ss[i]-'0';
if(tied[root][id]==0){
ott++;
tied[root][id]=ott;
}
root=tied[root][id];
sum[root]++;//此时的root 表示父节点的标号 sum则表示被访问的次数
}
}
int search(){
int root=0;
int len=strlen(ss);
for(int i=0;i<len;i++){
int id=ss[i]-'0';
if(tied[root][id]==0)return 0;
root=tied[root][id];//更新
}
return sum[root];
}
int main(){
int n,m,z;
cin>>n;
while(n--){
memset(sum,0,sizeof(sum));
memset(tied,0,sizeof(tied));
cin>>m>>z;//m是给的字符典 z是询问的次数
ott=0;
while(m--){
cin>>ss;
insert();
}//获取并建立我们的字典树;
int ans=0;
while(z--){
cin>>ss;
ans=search();
cout<<ans<<endl;
}
}
return 0;
}
## ```有没有大佬帮忙看看我这个代码为什么会出现wa和tle的问题,回复闭关,谢谢啦谢谢啦。
by prolu @ 2024-04-17 13:58:20
我看了题解下面的其他人的回复,这道题似乎卡memset,也许是这个导致了tle
by only_a_speaker @ 2024-04-17 15:17:05
您好,题目并不会“卡memset”,而会卡不正确的时间复杂度。请不要每次都对整个数组调用 memset,否则时间复杂度会超标;请通过传参指定合理的清零范围。