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\n":"YES\n"); 56 } 57 return 0; 58 }
原文：https://www.cnblogs.com/cutepota/p/12589695.html