16pts不知道错哪了？？？

fanjiayu666 @ 2024-10-23 21:04:30

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int change(char a){
    if(a>='A'&&a<='Z')return a-'A';
    else if(a>='a'&&a<='z')return a-'z'+26;
    else if(a>='0'&&a<='9')return a-'0'+26*2;

}
struct trie{
    int nex[3000010][26*2+10],cnt;
    int end[3000010];
    void emmset(int a){
        for(int i=1;i<=a;i++)memset(nex[i],0,sizeof(nex[i]));
        for(int i=1;i<=a;i++)end[i]=0;
    }
    void insert(char s[],int l){
        int p=0;
        for(int i=0;i<l;i++){
            int c=change(s[i]);
            if(!nex[p][c])nex[p][c]=++cnt;
            p=nex[p][c];
        }
        end[p]++;
    }
    int find(char s[],int l){
        int p=0;
        for(int i=0;i<l;i++){
            int c=change(s[i]);
            if(!nex[p][c])return 0;
            p=nex[p][c];
        }
        return end[p];
    }
};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        trie tree;
        cin>>n>>m;
        tree.emmset(n);
        for(int i=1;i<=n;i++){
            char s[3000010];
            cin>>s;
            tree.insert(s,strlen(s)-1);
        }
        for(int i=1;i<=m;i++){
            char s[3000010];
            cin>>s;
            cout<<tree.find(s,strlen(s)-1)<<endl;
        }
    }
}

by ALANYQ @ 2024-10-23 21:05:37

哦？

by ronkeyson @ 2024-10-23 21:56:26

小结错误（emmm，亿点多）：

1. 外面 insert 和 find 函数传递的字符串长度就已经 -1 了，里面重复谢了小于，因此外面改成这样就行了：

           tree.insert(s,strlen(s));
           cout<<tree.find(s,strlen(s))<<endl;

2. ```cpp void insert(char s[],int l){ int p=0; for(int i=0;i<l;i++){ int c=change(s[i]); if(!nex[p][c])nex[p][c]=++cnt; p=nex[p][c]; end[p]++; //这里改上来 } // end[p]++; } ```
3. ```cpp else if(a>='a'&&a<='z')return a-'a'+26; ```
4. 初始化函数里应该从零开始初始化，结尾是总节点数而不是 n，最后将 cnt 重新设置为 0，如下：（注：这里我直接把传参去掉改成 cnt 了，所以主函数里的 n 要去掉）

   void emmset(){
       for(int i=0;i<=cnt;i++)memset(nex[i],0,sizeof(nex[i]));
       for(int i=0;i<=cnt;i++)end[i]=0;
       cnt = 0;
   }

   最后交一发就过啦~

https://www.luogu.com.cn/record/184361799

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int change(char a){
    if(a>='A'&&a<='Z')return a-'A';
    else if(a>='a'&&a<='z')return a-'a'+26;
    else if(a>='0'&&a<='9')return a-'0'+26*2;

}
struct trie{
    int nex[3000010][26*2+10],cnt;
    int end[3000010];
    void emmset(){
        for(int i=0;i<=cnt;i++)memset(nex[i],0,sizeof(nex[i]));
        for(int i=0;i<=cnt;i++)end[i]=0;
        cnt = 0;
    }
    void insert(char s[],int l){
        int p=0;
        for(int i=0;i<l;i++){
            int c=change(s[i]);
            if(!nex[p][c])nex[p][c]=++cnt;
            p=nex[p][c];
            end[p]++;
        }
    }
    int find(char s[],int l){
        int p=0;
        for(int i=0;i<l;i++){
            int c=change(s[i]);
            if(!nex[p][c])return 0;
            p=nex[p][c];
        }
        return end[p];
    }
};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        trie tree;
        cin>>n>>m;
        tree.emmset();
        for(int i=1;i<=n;i++){
            char s[3000010];
            cin>>s;
            tree.insert(s,strlen(s));
        }
        for(int i=1;i<=m;i++){
            char s[3000010];
            cin>>s;
            cout<<tree.find(s,strlen(s))<<endl;
        }
    }
}

by fanjiayu666 @ 2024-10-24 13:55:51

very thx. 已关 @ronkeyson

by fanjiayu666 @ 2024-10-24 13:56:39

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%dalao

by ronkeyson @ 2024-10-24 21:05:47

蟹蟹~（CSP 要来了好紧张 QAQ)