萌新刚学Trie,求助模板题
查看原帖
萌新刚学Trie,求助模板题
338786
mushroom_knight楼主2020/12/12 22:40

Rt,交上去不知道为什么WA了三个点。

看不出来哪里有问题 /kk


#include<bits/stdc++.h>
using namespace std;

namespace tree{
    const int si=1e5+10;
    const int k=10;
    int trie[si*k][26];
    bool end[si*k];
    int tot=1;

    void insert(string str){
        int len=str.size();
        int p=1;
        for(register int k=0;k<len;++k){
            int ch=str[k]-'a';
            if(trie[p][ch]==0){
                trie[p][ch]=++tot;
                p=trie[p][ch];
            }
            end[p]=true;
        }
    }

    bool search(string str){
        int len=str.size();
        int p=1;
        for(register int k=0;k<len;++k){
            p=trie[p][str[k]-'a'];
            if(p==0){
                return false;
            }
        }
        return end[p];
    }

    void init(){
        memset(trie[0],0,sizeof(trie[0]));
        memset(end,0,sizeof(end));
        tot=1;
    }
}

int n,m;

string s[tree::si/10];
map<string,bool>mp;

int main(){
    tree::init();
    scanf("%d",&n);
    for(register int i=1;i<=n;++i){
        cin>>s[i];
        tree::insert(s[i]);
    }
    scanf("%d",&m);
    for(register int i=1;i<=m;++i){
        string get;
        cin>>get;
        if(tree::search(get)==true){
            if(mp[get]==true){
                cout<<"REPEAT"<<endl;
            }
            else{
                cout<<"OK"<<endl;
                mp[get]=true;
            }
        }
        else{
            cout<<"WRONG"<<endl;
        }
    }
    return 0;
}
2020/12/12 22:40
加载中...