题意：给一组互不相同的序列，问其中是否有字符串是另一字符串的前缀
思路：Trie树水题
1 #include<iostream>
2 using namespace std;
3 #define MAXN 100010
4 struct node
5 {
6 bool end;
7 node *next[10];
8 };
9 node *root;
10 int top=0;
11 bool is_new,ans;
12 node memo[MAXN];
13 void insert(node *t,char c[],int i)
14 {
15 if(t->end)
16 {
17 ans=1; return ;
18 }
19 if(i==strlen(c))
20 {
21 t->end=1; return ;
22 }
23 int x=c[i]-'0';
24
25 if(t->next[x]==NULL)
26 {
27 is_new=1;
28 node *p=&memo[top++]; t->next[x]=p;
29 }
30 insert(t->next[x],c,i+1);
31 }
32 int main()
33 {
34 char c[11];
35 int T,n;
36 int i;
37 scanf("%d",&T);
38 while(T--)
39 {
40 scanf("%d",&n);
41 memset(memo,0,sizeof(memo));
42 top=0; root=&memo[top++];
43 ans=0;
44 for(i=1;i<=n;i++)
45 {
46 is_new=0;
47 scanf("%s",c);
48 if(!ans) insert(root,c,0);
49 if(!is_new) ans=1;
50 }
51 if(ans) printf("NO\n");
52 else printf("YES\n");
53 }
54 return 0;
55 }