hdu杭电1671 / poj3630 字典树

题意：输入n串数字找出是否有存在串的前缀与另一个串相同如果存在输出NO否则输出YES

思路：用字典树解决标记字典树总串的结尾查找出一个串内部是否有被标记的节点如果有那么说明存在前缀相同的串

在插入字典树的时候判断是否存在 cin poj tle了还是换成gets才过。。。

AC代码：

 1 #include "iostream"
 2 #include "stdio.h"
 3 #include "string.h"
 4 using namespace std;
 5 
 6 using namespace std ;
 7 typedef long long ll;
 8 #define mem(a) memset(a,0,sizeof(a))
 9 
10 typedef struct Trie
11 {
12     bool isword;
13     struct Trie *next[10];
14 }*Trie_pointer;
15 
16 Trie trie[300005];
17 
18 int tot,flag;
19 
20 void Insert(Trie_pointer root, char *s)
21 {
22     if(*s == '')
23         return;
24     char *p = s;
25     Trie_pointer tmp,t = root;
26     while(*p != '')
27     {
28         if(t->next[*p - '0'] == NULL)
29         {
30             tmp = &trie[tot++];
31             t->next[*p - '0'] = tmp;
32         }
33         t = t->next[*p - '0'];
34         p++;
35         if(t->isword == 1)
36             flag = 1;
37     }
38     t->isword = 1;
39     for(int i=0; i<10; i++)
40     {
41         if(t->next[i] != NULL)
42             flag = 1;
43     }
44 }
45 
46 int main()
47 {
48     Trie root;
49     char s[2005];
50     int i,n,t;
51     cin>>t;
52     while(t--)
53     {
54         memset(trie,0,sizeof(trie));
55         memset(&root,0,sizeof(root));
56         tot=0;
57         cin>>n;
58         getchar();
59         while(n--)
60         {
61             gets(s);
62             if(!flag)
63                 Insert(&root,s);
64         }
65         if(flag)
66             printf("NO
");
67         else
68             printf("YES
");
69         flag = 0;
70     }
71     return 0;
72 }