求条

KMYC @ 2024-10-07 10:49:47

#include<bits/stdc++.h>
using namespace std;
const int N=3000010;
struct node{ int child[128],cnt; }trie[N];
int tot;
void insert(string s){
    int len=s.size();
    int cur=0;
    for(int i=0;i<len;i++){
        if(trie[cur].child[s[i]]==0) trie[cur].child[s[i]]=++tot;
        trie[cur].cnt++;
        cur=trie[cur].child[s[i]];
    }
}
int find(string s){
    int len=s.size();
    int cur=0;
    for(int i=0;i<len;i++){
        if(trie[cur].child[s[i]]==0) return 0;
        cur=trie[cur].child[s[i]];
    }
    return trie[cur].cnt;
}
int t,n,q;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>q;
        for(int i=1;i<=tot;i++){
            trie[i].cnt=0;
            for(int j=0;j<128;j++) trie[i].child[j]=0;
        }
        tot=0;
        string str;
        for(int i=1;i<=n;i++){
            cin>>str;
            insert(str);
        }
        while(q--){
            cin>>str;
            cout<<find(str)<<"\n";
        }
    } 
    return 0;
}

by KMYC @ 2024-10-07 10:50:02

52pts wa

by ronkeyson @ 2024-10-22 23:50:04

@KMYC

问题出在这里：

        for(int i=1;i<=tot;i++){
            trie[i].cnt=0;
            for(int j=0;j<65;j++) trie[i].child[j]=0;
        }

这里的 i 应当从 0 开始 再把上面那两句对调一下

        trie[cur].cnt++;
        cur=trie[cur].child[s[i]];

变成这样：

        cur=trie[cur].child[s[i]];
        trie[cur].cnt++;

提交

#include<bits/stdc++.h>
using namespace std;
const int N=3000010;
struct node{ int child[128],cnt; }trie[N];
int tot;
void insert(string s){
    int len=s.size();
    int cur=0;
    for(int i=0;i<len;i++){
        if(trie[cur].child[s[i]]==0) trie[cur].child[s[i]]=++tot;
        cur=trie[cur].child[s[i]];
        trie[cur].cnt++;
    }
}
int find(string s){
    int len=s.size();
    int cur=0;
    for(int i=0;i<len;i++){
        if(trie[cur].child[s[i]]==0) return 0;
        cur=trie[cur].child[s[i]];
    }
    return trie[cur].cnt;
}
int t,n,q;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>q;
        for(int i=0;i<=tot;i++){
            trie[i].cnt=0;
            for(int j=0;j<128;j++) trie[i].child[j]=0;
        }
        tot=0;
        string str;
        for(int i=1;i<=n;i++){
            cin>>str;
            insert(str);
        }
        while(q--){
            cin>>str;
            cout<<find(str)<<"\n";
        }
    } 
    return 0;
}

by KMYC @ 2024-10-23 21:15:50

@ronkeyson %%%

by ronkeyson @ 2024-10-23 21:24:51

~