数据结构之Trie树

刚开始套字典树将字符串末尾标记查询到末尾时标记动态的超时了参考着别人的写了个静态的过了 172MS

View Code

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 struct node
 6 {
 7     int count;
 8     int next[11];
 9     
10 }tr[100010];
11 int flag,num;
12 void node1()
13 {
14     tr[num].count = 0;
15     memset(tr[num].next,0,sizeof(tr[num].next));
16 }
17 void creat(char *str)
18 {
19     int i,j,k=strlen(str),d;
20     int f = 0,x = 0;
21     for(i = 0 ; i < k  ;i++)
22     {
23         d = str[i]-48;        
24         if(!f&&tr[x].count==1)
25         {
26             flag = 0;
27         }
28         if(tr[x].next[d] == 0)
29         {
30             num++;
31             node1();
32             tr[x].next[d] = num;                    
33             f = 1;
34         }
35         x = tr[x].next[d];                    
36     }
37     if(!f)
38         flag = 0;
39     tr[num].count = 1;
40 }
41 int main()
42 {
43     int i,j,k,n,t;
44     char c[11];
45     scanf("%d",&t);
46     while(t--)
47     {
48         scanf("%d%*c",&n);
49         memset(tr,0,sizeof(tr));
50         flag = 1;
51         num = 0;
52         while(n--)
53         {
54             gets(c);
55             if(flag)
56             creat(c);
57         }
58         if(flag)
59             printf("YES\n");
60         else
61             printf("NO\n");
62     }
63     return 0;
64 }

动态的会超时

View Code

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 struct node
 6 {
 7     int count;
 8     node *next[11];
 9     node()
10     {
11         count = 0;
12         memset(next,NULL,sizeof(next));
13     }
14 };
15 int flag;
16 void creat(char *str,struct node *root)
17 {
18     int i,j,k=strlen(str),d;
19     int f = 0;
20     struct node *p = root;
21     for(i = 0 ; i < k  ;i++)
22     {
23         d = str[i]-48;
24         if(!f&&p->count == 1)
25         {
26             flag = 0;
27         }
28         if(p->next[d] == NULL)
29         {
30             p->next[d]=new node;
31             f = 1;
32         }            
33         p = p->next[d];
34     }
35     if(!f)
36         flag = 0;
37     p->count = 1;
38 }
39 int main()
40 {
41     int i,j,k,n,t;
42     char c[11];
43     scanf("%d",&t);
44     while(t--)
45     {
46         scanf("%d%*c",&n);
47         flag = 1;
48         struct node *root = new node;
49         while(n--)
50         {
51             gets(c);
52             if(flag)
53             creat(c,root);
54         }
55         if(flag)
56             printf("YES\n");
57         else
58             printf("NO\n");
59     }
60     return 0;
61 }