hdu 1671 复习字典树

#include<cstdio>

#include<iostream>

#include<string>

#include<cstdlib>

#define maxn 10

using namespace std;

struct Tri

{

    Tri*next[maxn];

    int num;

};

Tri *root;

void buildTri(string ss)//建树的过程是一个动态的过程 动插的过程

{

    Tri *p=root,*q;

    for(int i=;i<ss.size();i++)

    {

        int id=ss[i]-'0';

        if(p->next[id]==NULL)

        {

            q=(Tri*)malloc(sizeof(Tri));

            q->num=;

            for(int j=;j<maxn;j++) q->next[j]=NULL;

            p->next[id]=q;

            p=p->next[id];

        }

        else p=p->next[id],p->num++;

    }

    p->num=-;// 作为结束的标志

}

int findTri(string ss)

{

    Tri *p=root,*q;

    for(int i=;i<ss.size();i++)

    {

        int id=ss[i]-'0';

        p=p->next[id];

        if(p==NULL) return;

        if(p->num==-) return -;

    }

    return -;

}

void del(Tri *root)

{

    Tri *zz=root;

    if(zz==NULL) return;

    for(int i=;i<maxn;i++)

    {

        if(zz->next[i]!=NULL) del(zz->next[i]);

    }

    free(zz);

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        root=(Tri*)malloc(sizeof(Tri));

        for(int i=;i<maxn;i++) root->next[i]=NULL;

        root->num=;

        int ret;

        cin>>ret;

        string ss;

        int flag=;

        while(ret--)

        {

            cin>>ss;

            if(findTri(ss)==-) flag=;

        //    cout<<flag<<endl;

            buildTri(ss);

        }

        del(root);

        if(flag) cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

    return;

}
巴特西

hdu 1671 复习字典树

最新文章

热门文章
