求大佬解释为什么tle

Halen1happy @ 2024-12-14 17:53:29

#include<bits/stdc++.h>
using namespace std;
//字典树的基本操作：查找，插入，删除
//字典树的应用 串的快速检索，串排序，前缀统计及判断，最长公共前序
//trie树是字典树 
const int N=3000005;
int son[N][65],cnt[N],idx;
char str[N];
int ge(char x){
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
}
//插入字符串 
void insert(char *str){
    int p=0;
    for(int i=0;i<strlen(str);i++){
        int u=ge(str[i]);
        if(!son[p][u])
         son[p][u]=++idx;
        p=son[p][u];
        cnt[p]++;
    }
}
//查询字符串
int query(char *str){
    int p=0;
    for(int i=0;i<strlen(str);i++){
        int u=ge(str[i]);
        if(!son[p][u]) 
        return 0;
        p=son[p][u];
    }
    return cnt[p];
} 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        idx=0;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=122;j++){
                son[i][j]=0;
            }
        }
        for(int i=1;i<=N;i++){
            cnt[i]=0;
        }
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%s",str);
            insert(str);
        }
        for(int i=1;i<=m;i++){
            scanf("%s",str);
             printf("%d\n",query(str));
        }   
    }

    return 0;
} 

by kevinZ99 @ 2024-12-14 18:08:52

@Halen1happy

1、清空的时候只需要清空改变过的地方。

2、字符串长度用变量存。

#include<bits/stdc++.h>
using namespace std;
//字典树的基本操作：查找，插入，删除
//字典树的应用 串的快速检索，串排序，前缀统计及判断，最长公共前序
//trie树是字典树 
const int N=3000005;
int son[N][65],cnt[N],idx;
char str[N];
int ge(char x){
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
}
//插入字符串 
void insert(char *str){
    int p=0;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        int u=ge(str[i]);
        if(!son[p][u])
         son[p][u]=++idx;
        p=son[p][u];
        cnt[p]++;
    }
}
//查询字符串
int query(char *str){
    int p=0;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        int u=ge(str[i]);
        if(!son[p][u]) 
        return 0;
        p=son[p][u];
    }
    return cnt[p];
} 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        idx=0;
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%s",str);
            insert(str);
        }
        for(int i=1;i<=m;i++){
            scanf("%s",str);
             printf("%d\n",query(str));
        }   
        for(int i=0;i<=idx;i++){
            for(int j=0;j<=64;j++){
                son[i][j]=0;
            }
        }
        for(int i=0;i<=idx;i++){
            cnt[i]=0;
        }
    }
    return 0;
}

by Halen1happy @ 2024-12-14 18:10:26

@kevinZ99哇哇哇哇哇谢谢谢谢大佬

by Halen1happy @ 2024-12-14 18:13:49

@kevinZ99好厉害！！！