Consistency Checker LightOJ - 1129

Consistency Checker LightOJ - 1129
SETI is receiving some weird signals for the past few days. After converting them to our number system they found out that some numbers are repeating. Due to travelling millions of miles signal gets distorted. Now they asked you check the consistency of their data sets. The consistency is that, no number is the prefix another number in that data set. Let’s consider a data set:

1.  123
   

2.  5123456
   

3.  123456
   

In this data set, numbers not consistent, because the first number is the prefix of the third one.

Input
Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with an integer n (1 ≤ n ≤ 10000) denoting the total numbers in their list. Each of the next n lines contains one unique phone number. A number is a sequence of digits and has length from 1 to 10.

Output
For each case, print the case number and ‘YES’ if the list is consistent or ‘NO’ if it’s not.

Sample Input
2

3

911

97625999

91125426

5

113

12340

123440

12345

98346

Sample Output
Case 1: NO

Case 2: YES

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char a[15];
int tree[100002][10],vis[100002];
// tree是树,vis是记录每一个单词是否存在
int tal,f;
void create(char a[]);
int main()
{
    int T;
    cin>>T;
    int k=T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(tree,0,sizeof(tree));
        tal=1;
        f=0;
        int n;
        cin>>n;
        while(n--)
        {
            memset(a,0,sizeof(a));
            scanf("%s",a);
            create(a);   //创建树
        }
        if(f==1)printf("Case %d: NO\n",k-T);
        else printf("Case %d: YES\n",k-T);
    }
    return 0;
}
void create(char a[])
{
    int root=0;  //每次从树跟开始
    int len=strlen(a);
    for(int i=0; i<len; i++)
    {
        int di=a[i]-'0';   //转化成0-9的数字
        if(tree[root][di]==0) // 如果不存在，则创造一个节点
        {
            tree[root][di]=tal++;
        }
        else if(tree[root][di]&&i==len-1)
        {            //如果这个节点存在，并且是这个单词的最后一个
                     //则说明，之前有单词包涵这个单词
            f=1;
        }
        root=tree[root][di];
        if(vis[root]==1)
        {            //如果==1说明现在这个单词包涵前面某个单词
            f=1;
        }
    }
    vis[root]=1;  //记录每个单词
}