字典树代码tle的疑问

P8306 【模板】字典树

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,否则时间复杂度会超标;请通过传参指定合理的清零范围。


|