电话列表（字典树）------------Five-菜鸟级

                                                       电话列表

时限：1000 MS		内存限制：65536K
提交材料共计：34731		接受： 9962

描述

给定一个电话号码列表，确定它是否一致，因为没有号码是另一个号码的前缀。假设电话目录列出了这些号码：

• 紧急911

• 爱丽丝97 625 999

• 鲍勃91 12 54 26

在这种情况下，不可能打电话给Bob，因为一旦您拨了Bob电话号码的前三位数，中央就会将您的电话直接打到紧急线路。所以这个名单就不一致了。

输入

输入的第一行给出一个整数，1≤t≤40，测试用例的数量。每个测试用例从n，电话号码，在一条单独的线路上，1≤。n≤10000。然后：n每行上有一个唯一电话号码的线路。电话号码最多是十位数。

输出量

对于每个测试用例，如果列表一致，输出“是”，否则输出“否”。

样本输入

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

样本输出

NO
YES

题目链接：http://poj.org/problem?id=3630

 题解： 这是trie(字典)树模板题，字典树插入操作的运用，插入一个单词是 在单词最后一个字符打上结束标记。插入新单词时，不会遇到单词结束标记，则不会起冲突 满足条件。

 想了解 字典树（点击即可）

AC代码：

  

   

    

     

    
    

     

      #include<stdio.h> 
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #define N 60001
     
    
   

    

     

    
    

     

      int trie[N][13]; 
     
    
   

    

     

    
    

     

      int sum[N]; //存从根节点到单词（前缀）的单词数
     
    
   

    

     

    
    

     

      int tot; 
     
    
   

    

     

    
    

     

      int flag;
     
    
   

    

     

    
    

     

      void insert(char *s){//插入单词
     
    
   

    

     

    
    

     
	if(flag) return;//已经冲突了 则不必插入单词了 
     
    
   

    

     

    
    

     
	int i,id,len,root=0; len=strlen(s);
     
    
   

    

     

    
    

     
	for(i=0;i<len;i++)
     
    
   

    

     

    
    

     

      	{   id=s[i]-'0';
     
    
   

    

     

    
    

     
		if(!trie[root][id])trie[root][id]=++tot;//给字符节点编号 
     
    
   

    

     

    
    

     

      		 root=trie[root][id]; //更新字符节点 
     
    
   

    

     

    
    

     
		 if(sum[root]==-1){flag=1;return;}//如果遇到下一个字符节点为某单词结尾标记 -1 则不符合要求 
     
    
   

    

     

    
    

     

      		  sum[root]++;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
       if(sum[root]==1)sum[root]=-1; 
     
    
   

    

     

    
    

     
	   //在满足不是前缀 单词最后一个字符为标记为 -1 
     
    
   

    

     

    
    

     
	   else flag=1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {   char s[12]; int T,n; 
     
    
   

    

     

    
    

     
	  scanf("%d",&T);
     
    
   

    

     

    
    

     
	  while(T--){
     
    
   

    

     

    
    

     
	      memset(trie,0,sizeof(trie));
     
    
   

    

     

    
    

     
	      memset(sum,0,sizeof(sum));
     
    
   

    

     

    
    

     

      	      flag=0;tot=0;
     
    
   

    

     

    
    

     
	      scanf("%d",&n);
     
    
   

    

     

    
    

     
	      while(n--)scanf("%s",&s),insert(s);//输入单词表 
     
    
   

    

     

    
    

     
	      if(flag==1) printf("NO\n");
     
    
   

    

     

    
    

     
	      else printf("YES\n");
     
    
   

    

     

    
    

     

      	  }	 
     
    
   

    

     

    
    

     
	return 0;	
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/82980927