HDU 1247 Hat’s Words

字典树模板题
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1247
View Code
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #define N 26
 5 #define maxn 1000000
 6 char s[50001][101];
 7 struct node
 8 {
 9     int flag;
10     struct node *next[N];
11 }tree[maxn];
12 int t=0;
13 struct node *creat()
14 {
15     int i;
16     struct node *p;
17     p=&tree[t++];
18     p->flag=0;
19     for(i=0;i<N;i++)
20     {
21         p->next[i]=NULL;
22     }
23     return p;
24 }
25 void insert(struct node **root,char *s)
26 {
27     int i,k;
28     struct node *p;
29     if(!(p=*root))
30     {
31         p=*root=creat();
32     }
33     i=0;
34     while(s[i])
35     {
36         k=s[i++]-'a';
37   if(p->next[k]==0)
38             p->next[k]=creat();
39         p=p->next[k];
40     }
41     p->flag=1;
42 }
43 int search(struct node **root,char *s)
44 {
45     int i=0,k;
46     struct node *p;
47     if(!(p=*root))
48     {
49         return 0;
50     }
51     while(s[i])
52     {
53         k=s[i++]-'a';
54         if(!(p->next[k]))
55             return 0;
56         p=p->next[k];
57     }
58     return p->flag;
59 }
60 int main()
61 {
62     char s1[101],s2[101],s3[101];
63     int l,i,j,k,c=0;
64     struct node *root=NULL;
65     while(~scanf("%s",s[c]))
66     {
67         insert(&root,s[c]);  
68         c++;
69   if(c==6)
70    break;
71     }
72     for(i=0;i<c;i++)
73     {
74         memset(s1,0,sizeof(s1));
75         l=strlen(s[i]);
76         for(j=0;j<l;j++)
77         {
78             s1[j]=s[i][j];
79             if(search(&root,s1))
80             {
81                 memset(s2,0,sizeof(s2));
82                 for(k=j+1;k<l;k++)
83                     s2[k-j-1]=s[i][k];
84                 if(search(&root,s2))
85                 {
86                     puts(s[i]);
87                     break;
88                 }
89             }
90         }
91     }
92     return 0;
93 }