题解 P2580 【于是他错误的点名开始了】

cjtz · 2017-08-11 12:18:26 · 题解

不能使用数组来存Trie树，会超内存，用指针动态管理内存空间

两种Trie树：

1.每个节点存储26个指针

2.左儿子-右兄弟表示法

第一种方法更为消耗内存，查询复杂度为O(m)

第二种方法节省内存，但需要遍历节点的儿子链表，查询较为耗时

无论用哪种方法都给节点增加一个bool visited属性，表示已经点过名，find作为三态函数，这样可以避免开两个Trie树

第一种方法的评测结果：1726ms / 68.88MB

第二种方法的评测结果：1489ms / 19.78MB

可以看到第二种方法比第一种方法耗时短，这大概是因为第一种方法节点的初始化较为耗时，可以去掉构造函数，全局声明trie树

声明：给出的代码没有写字符串的末尾判定，这道题居然没有出错，请同学们自行修改一下节点和find函数

第一种

#include<cstring>
#include<iostream>
using namespace std;
struct Trie
{
    static const int sigma_size=26;
    static const int zero=97;
    struct Node
    {
        Node *ch[sigma_size];
        bool visited;
        Node()
        {
            for(int i=0;i<sigma_size;i++)
                ch[i]=NULL;
            visited=0;
        }
    }root;
    void insert(string x)
    {
        Node *t=&root;
        for(int i=0;i<x.size();i++)
        {
            if(t->ch[x[i]-zero]==NULL)
                t->ch[x[i]-zero]=new Node;
            t=t->ch[x[i]-zero];
        }
    }
    int find(string x)
    {
        Node *t=&root;
        for(int i=0;i<x.size();i++)
        {
            if(t->ch[x[i]-zero]==NULL)    return 0;
            t=t->ch[x[i]-zero];
        }
        if(t->visited)    return 2;
        t->visited=1;
        return 1;
    }
    void del(string a,Node *x)
    {
        if(!find(a))    return;
        if(a.size()==1)    delete x->ch[a[0]-zero];
        else
        {
            del(a.substr(1),x->ch[a[0]-zero]);
            delete x->ch[a[0]-zero];
        }
        x->ch[a[0]-zero]=NULL;
    }
};
Trie T;
int main()
{
    int n,t;
    string s;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        T.insert(s);
    }
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        t=T.find(s);
        if(t==0)
            cout<<"WRONG";
        else if(t==1)
            cout<<"OK";
        else
            cout<<"REPEAT";
        cout<<endl;
    }
    return 0;
}

第二种

include<cstring>

include<iostream>

using namespace std;

class Trie

{ public:

        struct Node
        {
            Node *lc;
            Node *rb;
            char ch;
            bool visited;
            Node(){    lc=NULL;rb=NULL;ch=0;visited=0;}
        };
        Node root;
        void insert(string x)
        {
            Node *t=&root;
            Node *s;
            for(int i=0;i<x.size();i++)
            {
                if(t->lc==NULL)
                {
                    t->lc=new Node;
                    t->lc->ch=x[i];
                }
                s=have_child(t,x[i]);
                if(s!=NULL)
                    t=s;
                else
                {
                    s=t->lc->rb;
                    t->lc->rb=new Node;
                    t->lc->rb->rb=s;
                    t->lc->rb->ch=x[i];
                    t=t->lc->rb;
                }
            }
        }
        int find(string x)
        {
            Node *t=&root;
            Node *s;
            for(int i=0;i<x.size();i++)
            {
                s=have_child(t,x[i]);
                if(s==NULL)    return 0;
                t=s;
            }
            if(t->visited)    return 2;
            t->visited=1;
            return 1;
        }
        void del(Node *x,string a)
        {
            if(!find(a))    return;
            if(a.size()==1)    delete have_child(x,a[0]);
            else
            {
                Node *s=have_child(x,a[0]);
                del(s,a.substr(1));
                delete s;
            }
        }
private:

        Node *have_child(Node *t,char c)
        {
            t=t->lc;
            while(t!=NULL)
            {
                if(t->ch==c)    return t;
                t=t->rb;
            }
            return NULL;
        }
};
Trie T;
int main()
{
    int n,t;
    string s;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        T.insert(s);
    }
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        t=T.find(s);
        if(t==0)
            cout<<"WRONG";
        else if(t==1)
            cout<<"OK";
        else
            cout<<"REPEAT";
        cout<<endl;
    }
    return 0;
}