Phone List

Description
有N个数字串(N<=10000，串长最多12位）
问其中是不是有某个串是另一个串的子串，有输出NO，否则输出YES。
Input
Output
Sample Input
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
Sample Output
NO
YES

sol:

1.将所有的单词先加入Trie树。这里是统计看有没有单词是别人的前缀，因此在建树时，每个结点的字符，有可能不止出现一次，因此我们要记录下每个结点出现的次数。如下样例：

2.依次查询每一个单词，查询时，只要查找到某个单词的结束位置时，如果该结点出现的次数-1（减它自己这一次）还大于1的话，说明还有其它单词也同样有该单词的这些字符，即该查询单词是另一个单词的前缀，查找成功，输出结果。

代码如下：

 1 #include<cstring>
 2 #include<iostream>
 3 using namespace std;
 4 int a[100010][11],tot,End[100010]; //a数组的第二维，因为是0..9的数字，所以定义11就可以了
 5 void ins(char *str)// 插入单词 
 6 {
 7     int n=strlen(str),p=0;
 8     for(int i=0;i<n;i++)
 9     {
10         int l=str[i]-'0';
11         if(!a[p][l])
12               a[p][l]=++tot;
13         p=a[p][l];
14         End[p]++;//编号p在单词中出现的次数增加 
15     }
16 }
17 int find(char *str)
18 {
19     int n=strlen(str),p=0;
20     for(int i=0;i<n;i++)
21     {
22         int l=str[i]-'0';
23         p=a[p][l];
24         if(!p)return 0;
25     }
26     return End[p]-1;
27     //因为在查找的时候，一定会找到自己，该点出现的次数-1后 
28     //如果End[p]-1仍大于0，说明还有其它单词经过该点，该单词是其它单词的前缀 
29 }
30 char str[10010][11];
31 int main()
32 {
33     int t;
34     scanf("%d",&t);
35     while(t--)
36     {
37         tot=0;
38         memset(a,0,sizeof(a));
39         memset(str,0,sizeof(str));
40         memset(End,0,sizeof(End));
41         int n;
42         scanf("%d",&n);
43         for(int i=1;i<=n;i++)//建Trie 
44         {
45             scanf("%s",str[i]);
46             ins(str[i]);
47         }
48         bool flag=0;
49         for(int i=1;i<=n;i++)//依次查找n个单词 
50             if(find(str[i]))//如果第i个单词是其它单词的前缀 
51             {
52                 flag=1;
53                 break;
54             }
55         printf(flag==1?"NO
":"YES
");
56     }
57     return 0;
58 }