30 07 2020

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;
} 
延伸阅读
  1. Burnside引理和polya定理
  2. [LuoguP3834]主席树模板题 静态区间K大
  3. [LuoguP4551]最长异或路径
  4. [LuoguP3950] 部落冲突
  5. [HNOI2012] 永无乡
  6. [BJOI2016] 回转寿司
  7. [Codeforces 547B] Mike and Feet
  8. 午夜杂谈
更多阅读
  1. 上一篇:[LuoguP3950] 部落冲突
  2. 下一篇:[LuoguP4551]最长异或路径
发表评论 抢沙发