[LuoguP2580]于是他错误的点名开始了

[LuoguP2580]于是他错误的点名开始了

Trie树模板,先摸索着写写,然后再填补一下可持久化Trie树的坑(我爱指针!

#include<bits/stdc++.h>
using namespace std;
struct Trie_Tree{
    bool tag,rpt;
    Trie_Tree*so[26];
    Trie_Tree(){
        tag=rpt=false;
        for(int i=0;i<=25;++i) so[i]=NULL;
    }
    void add(string s,int pos,int len){
        if(pos==len){
            tag=true;
            return;
        }
        if(so[s[pos]-'a']!=NULL) so[s[pos]-'a']->add(s,pos+1,len);
        else (so[s[pos]-'a']=new Trie_Tree)->add(s,pos+1,len);
    }
    int query(string s,int pos,int len){
        if(pos==len) {
            if(!tag) return -1;
            if(rpt) return 0;
            rpt=true;
            return 1;
        }
        if(so[s[pos]-'a']==NULL) return -1;
        else return so[s[pos]-'a']->query(s,pos+1,len);
    }
}*ttr;
int n,m;
char s[55];
int main(){
    scanf("%d",&n);
    ttr=new Trie_Tree;
    for(int i=1;i<=n;++i){
        scanf("%s",s);
        ttr->add(s,0,strlen(s));
    }
    scanf("%d",&m);
    int num,len;
    while(m--){
        scanf("%s",s);
        num=ttr->query(s,0,strlen(s));
        if(num==1) cout<<"OK"<<endl;
        else if(num==0) cout<<"REPEAT"<<endl;
        else if(num==-1) cout<<"WRONG"<<endl;
    }
    return 0;
}

留下回复