hdu 1247 Hat’s Words trie 简单字典树

这道题我用得静态树，发现静态树不如动态树啊，虽然时间快点，但是空间要求的也太离谱了~

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1247

大意：让你输入几个单词，然后看看这有几个是可以有其他的任意两个单词或者一个单词两次，连接组成的，把他们输出就可以了

代码

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 const int N=26;
 5 const int maxn=1000000;
 6 char s[50001][101];
 7 using namespace std;
 8 struct node
 9 {
10     int flag;
11     int count;
12     struct node *next[N];
13 }tree[maxn];
14 int t=0;
15 struct node *creat()
16 {
17     int i;
18     struct node *p;
19     p=&tree[t++];
20     p->count=1;
21     p->flag=0;
22     for(i=0;i<N;i++)
23     {
24         p->next[i]=NULL;
25     }
26     return p;
27 }
28 void insert(struct node **root,char *s)
29 {
30     int i,k;
31     struct node *p;
32     if(!(p=*root))
33     {
34         p=*root=creat();
35     }
36     i=0;
37     while(s[i])
38     {
39         k=s[i++]-'a';
40         if(p->next[k])
41             p->next[k]->count++;
42         else
43             p->next[k]=creat();
44         p=p->next[k];
45     }
46     p->flag=1;
47 }
48 int search(struct node **root,char *s)
49 {
50     int i=0,k;
51     struct node *p;
52     if(!(p=*root))
53     {
54         return 0;
55     }
56     while(s[i])
57     {
58         k=s[i++]-'a';
59         if(!(p->next[k]))
60             return 0;
61         p=p->next[k];
62     }
63     return p->flag;
64 }
65 int main()
66 {
67     char s1[101],s2[101],s3[101];
68     int l,i,j,k,c=0;
69     struct node *root=NULL;
70     while(~scanf("%s",s[c]))
71     {
72         insert(&root,s[c]);    
73         c++;
74 
75     }
76     for(i=0;i<c;i++)
77     {
78         memset(s1,0,sizeof(s1));
79         l=strlen(s[i]);
80         for(j=0;j<l;j++)
81         {
82             strncpy(s1,s[i],j);
83             if(search(&root,s1)&&search(&root,s[i]+j))
84             {
85                     puts(s[i]);
86                     break;
87             }
88         }
89     }
90     return 0;
91 }