学步园

题目链接:   hdu
1671

题目大意:   给出几串数组，是否存在一个串是另外一个串的前缀，是则输出"YES"

解题思路:   每个字符为单位建立一棵Trie树

                  字符串结尾的结点用w标记，然后插入时判断两种情况：

                  每次插入时如果经过之前插入字符串的结尾，则之前插入的字符串必定是前缀

                  每次插入时如果插到结尾还在之前的结点中，则现在插入的字符串必定是前缀

                  字典树的两种写法：

                  1.结点中包含next[ ]，加快查找时间，但耗费大量的空间

                  2.结点中不包含next[ ]，类似与建立有向图利用pre[ ]遍历，查找时间慢些，但省下很多空间

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10100
struct snode{
    char ch1;
    int next,w;  //第二种写法
}Tree[MAX*100];
char ch[20];
int pd,Index,pre[MAX*100];

void Add_edge(int a,char ch2,int len,int Tlen)  //建立有向图
{
    Tree[Index].ch1=ch2,Tree[Index].next=pre[a];
    if(len==Tlen)
        Tree[Index].w=1;
    pre[a]=Index++;
}

void DFS(int Star,int len,int Tlen,int kk)   //DFS遍历
{
    int i;
    if(len>Tlen||pd)
        return ;
    if(Tree[Star].w==1)
    {
        pd=1;
        return ;
    }
    for(i=pre[Star];i!=-1;i=Tree[i].next)
    {
        if(Tree[i].ch1==ch[len-1])   //遍历之前插入的点
        {
            if(Tree[i].w==1)  //小对大
            {
                pd=1;
                return ;
            }
            if(len==Tlen)
            {
                pd=1;
                return ;
            }
            DFS(i,len+1,Tlen,kk);
            return ;
        }
    }
    if(Tree[Star].w&&i==-1&&kk!=1)   //找到结尾结点
    {
        pd=1;
        return;
    }
    Add_edge(Star,ch[len-1],len,Tlen);
    DFS(Index-1,len+1,Tlen,kk);
}

int main()
{
    int t,n,i;
    scanf("%d",&t);
    while(t--)
    {
        pd=0;
        Index=1;
        memset(pre,-1,sizeof(pre));
        memset(Tree,0,sizeof(Tree));
        Tree[0].ch1='\0';
        Tree[0].next=-1;
        Tree[0].w=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%s",ch);
            if(!pd)        //找到前缀则停止搜索
            {
                DFS(0,1,strlen(ch),i);
            }
        }
        if(pd)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}