trie 求调，蜜汁 MLE

Engulf @ 2022-04-29 22:30:03

// author: TMJYH09
// create time: 2022/04/29 20:44:54
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 3e6+10;
int trie[N][123],idx=1;
int cnt[N];
void init(){
    for(int i=1;i<=idx;i++){
        cnt[i]=0;
        for(int j=0;j<123;j++){
            trie[i][j]=0;
        }
    }
    idx=1;
}
void insert(string s){
    int p=1;
    for(int i=0;i<s.size();i++){
        if(!trie[p][s[i]])trie[p][s[i]]=++idx;
        cnt[p]++;
        p=trie[p][s[i]];
    }
    cnt[p]++;
}
int query(string s){
    int p=1;
    for(int i=0;i<s.size();i++){
        if(!trie[p][s[i]])return 0;
        p=trie[p][s[i]];
    }
    return cnt[p];
}

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int T;cin>>T;
    while(T--){
        int n,q;cin>>n>>q;
        init();
        while(n--){string s;cin>>s;insert(s);}
        while(q--){string s;cin>>s;cout<<query(s)<<endl;}
    }
    return 0;
}

by PassName @ 2022-04-29 22:33:21

@TMJYH09 123*3e6显然炸了啊

by 蔡竣凯 @ 2022-04-29 22:33:29

给你个代码调（大雾

struct node{
    vector<int>s;
    int ne[30];
    bool f;
    node(){
        memset(ne,0,sizeof(ne));
        f=false;
    }
}head[MAXN];
int id;
void add(int x, string s){
    int num = 0;
    for(int i = 0;i < s.size(); i++){
        int len = s[i] - 'a' + 1;
        if(!head[num].ne[len]){
            head[num].ne[len] = ++id;
        }
        num = head[num].ne[len];
    }
    head[num].f = true;
    int len = head[num].s.size();
    if(len > 0 && head[num].s[len - 1] == x){
        return ;
    }
    head[num].s.push_back(x);
}
void find(string s){
    int num = 0;
    for(int i = 0;i < s.size(); i++){
        int len = s[i] - 'a' + 1;//ASCLL
        if(!head[num].ne[len]){
            return ;
        }
        num = head[num].ne[len];
    } 
    if(head[num].f){
        for(int i = 0;i < head[num].s.size(); i++){
            cout << head[num].s[i] << " ";
        }
    }
}

by PassName @ 2022-04-29 22:34:13

@TMJYH09 您可以尝试开一维数组解解试试

by joy2010WonderMaker @ 2022-05-01 12:49:08

@TMJYH09 改一下方式

by joy2010WonderMaker @ 2022-05-01 12:49:41

#include<bits/stdc++.h>
using namespace std;
int T,q,n,t[3000005][65],cnt[3000005],idx;
char s[3000005];
int getnum(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,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            t[p][c]=++idx;
        p=t[p][c];
        cnt[p]++;
    }
}
int find(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            return 0;
        p=t[p][c];
    }
    return cnt[p];
}
int main(){
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<=idx;i++)
            for(int j=0;j<=122;j++)
                t[i][j]=0;
        for(int i=0;i<=idx;i++)
            cnt[i]=0;
        idx=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            insert(s);
        }
        for(int i=1;i<=q;i++){
            scanf("%s",s);
            printf("%d\n",find(s));
        }
    }
    return 0;
}

by Engulf @ 2022-05-01 13:00:51

@joy2010WonderMaker thx