F



i



v



e



-



gr



ea



t
电话列表(字典树)


电话列表

时限: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;    
}