hdu1251 、1671、1247 字典树，，Trie树

时间：2011-04-28 来源：奋斗青春

这两天看了下字典树，，其实应该去年就学了的，不过去年集训时把这个给忽略了。。

思想很简单，也很容易理解：

根节点不包含字符，除根节点外每一个节点都只包含一个字符。

从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

每个节点的所有子节点包含的字符都不相同。

这个就像别人说的那样，是典型的以空间换时间，，所以写程序的时候要注意，，每次用完了要delete掉，否则会MLE的。。

这三道题目都比较简单，，就是简单的套模板就可以了，，

但是对于1247的方法不很满意，感觉先插入，然后再对每一个单词，一位一位的查，很浪费时间，不过竟然没有超时，感觉数据有点弱。。。寻找一种更好的方法。。

1671这个题目方法有很多，我是根据字符串的长度进行排序，，从大到小，再一个一个的插入，，注意一点，每一个测试实例之后需要把当前的Trie释放掉，或者delete掉，不然会MLE的。。

贴下1671的代码吧：

# include<stdio.h>
# include<stdlib.h>
# include<string.h>
# define MAX 10
struct Trie{
    int num;
    struct Trie *next[MAX];
};
struct node{
    int len;
    char str[15];
}s[10005];
int cmp(const void *a,const void *b)
{
    struct node *c=(struct node *)a;
    struct node *d=(struct node *)b;
    return d->len - c->len;
}
Trie *NewTrie()
{
    int i;
    Trie *p=new Trie;
    p->num=1;
    for(i=0;i<MAX;i++)
        p->next[i]=NULL;
    return p;
}
int Insert(Trie *p,char st[],int len1)
{
    Trie *temp=p;
    int i;
    for(i=0;i<len1;i++)
    {
        if(temp->next[st[i]-'0']==NULL)  
            temp->next[st[i]-'0']=NewTrie();
        else temp->next[st[i]-'0']->num++;
        temp=temp->next[st[i]-'0'];
    }
    if(temp->num >=2) return -1;
    else return 1;
}
void Delete(Trie *p)
{
    //删除整个树
    int i;
    if(p!=NULL)
    {
        for(i=0;i<MAX;i++)
            if(p->next[i]!=NULL) Delete(p->next[i]);
            delete p;
            p=NULL;
    }
}
int main()
{
    int i,n,ncase,ans;
    Trie *p;
    scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%s",s[i].str);
            s[i].len=strlen(s[i].str);
        }
        qsort(s+1,n,sizeof(s[1]),cmp);
        p=NewTrie();
        ans=0;
        for(i=1;i<=n;i++)
        {
            ans=Insert(p,s[i].str,s[i].len);
            if(ans==-1) break;
        }
        if(ans==-1) printf("NO\n");
        else printf("YES\n");
        Delete(p);
    }
    return 0;
}