hdu1247Hat’s Words（trie树）

http://acm.hdu.edu.cn/showproblem.php?pid=1247

先找某个单词是否为一个单词的前缀再用这个单词减去前缀判断剩下的部分是否为一个单词

View Code

 1 #include <iostream>
 2 #include<stdlib.h>
 3 #include<cstdio>
 4 #include<string.h>
 5 using namespace std;
 6 char c[50001][101];
 7 struct node
 8 {
 9     int flag;
10     node *next[27];
11     node()
12     {
13         flag = 0;
14         memset(next,NULL,sizeof(next));
15     }
16 };
17 void buildt(node *head,char *x)
18 {
19     int i,j =0 ,k,d;
20     k = strlen(x);
21     node *p = head;
22     for(i = 0 ; i < k ; i++)
23     {
24         d = x[i]-'a';
25         if(p->next[d]==NULL)
26         {
27             p->next[d] = new node;
28         }
29         p = p->next[d];
30     }
31     p->flag = 1;
32 }
33 int judge(node *head,char *x)
34 {
35     int i,d;
36     node *p = head;
37     while(*x!='\0')
38     {
39         d = *x-'a';
40         if(p->next[d]==NULL)
41         return 0;
42         p = p->next[d];
43         if(p->flag==1&&*(x+1)=='\0')//满足后一部分恰为一个单词
44         return 1;
45         x++;
46     }
47     return 0;
48 }
49 int search(node *head,char *x)
50 {
51     int i,d,k = strlen(x),t = 0;
52     node *p = head;
53     for(; *x != '\0' ; )
54     {
55         d = *x-'a';
56         if(p->next[d]==NULL)
57             return 0;
58         p = p->next[d];
59         if(p->flag == 1&&judge(head,x+1))//找到一个作为它前缀的单词 查看后一部分是不是为另一个单词
60         {
61             return 1;
62         }
63         x++;
64     }
65     return 0;
66 }
67 int main()
68 {
69     int i = 0,j,k,f;
70     node *head = new node;
71     while(gets(c[i])!=NULL)
72     {
73         buildt(head,c[i]);
74         i++;
75     }
76     for(j =0 ; j < i ; j++)
77     {
78         if(search(head,c[j]))
79         puts(c[j]);
80     }
81     return 0;
82 }