hdu 1251+hdu 1671（字典树）

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

一开始我是直接用STL做的，唉。。。没有经验那。。。orz...然后毫无疑问地超时了。。。

看别人blog说是字典树，说实话，第一次听到这个。。。就立马学了一下。。发现挺简单的。。。嘻嘻。。。

View Code

 1 #include<iostream>
 2 #include<cstring>
 3 const int N=26;
 4 using namespace std;
 5 struct Tire{
 6     int v;
 7     Tire *next[N];
 8 };
 9 Tire *root;
10 
11 //创建字典树
12 void CreateTire(char str[]){
13     int len=strlen(str);
14     Tire *p=root,*q;
15     for(int i=0;i<len;i++){
16         int id=str[i]-'a';
17         if(p->next[id]==NULL){
18             q=(Tire *)malloc(sizeof(Tire));
19             q->v=1;//一开始为1;
20             for(int i=0;i<N;i++){
21                 q->next[i]=NULL;
22             }
23             p->next[id]=q;
24             p=p->next[id];
25         }else {
26             p->next[id]->v++;
27             p=p->next[id];
28         }
29     }
30 }
31 
32 int FindTire(char str[]){
33     int len=strlen(str);
34     Tire *p=root;
35     for(int i=0;i<len;i++){
36         int id=str[i]-'a';
37         if(p->next[id]==NULL){
38             return 0;
39         }
40         p=p->next[id];
41     }
42     return p->v;
43 }
44 
45 int main(){
46     char str[100];
47     root=(Tire *)malloc(sizeof(Tire));
48     for(int i=0;i<N;i++){
49         root->next[i]=NULL;
50     }
51     while(gets(str)&&str[0]!='\0'){
52         CreateTire(str);
53     }
54     while(~scanf("%s",str)){
55         int ans=FindTire(str);
56         printf("%d\n",ans);
57     }
58     return 0;
59 }

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

值得一提的是，最后要释放动态申请的空间，不然就MLE。。。

View Code

 1 #include<iostream>
 2 #include<cstring>
 3 const int N=10;
 4 using namespace std;
 5 struct Tire{
 6     int v;
 7     Tire *next[N];
 8 };
 9 Tire *root;
10 
11 //创建字典树
12 void CreateTire(char str[]){
13     int len=strlen(str);
14     Tire *p=root,*q;
15     for(int i=0;i<len;i++){
16         int id=str[i]-'0';
17         if(p->next[id]==NULL){
18             q=(Tire *)malloc(sizeof(Tire));
19             q->v=1;
20             for(int i=0;i<N;i++){
21                 q->next[i]=NULL;
22             }
23             p->next[id]=q;
24             p=p->next[id];
25         }else {
26             p->next[id]->v++;
27             p=p->next[id];
28         }
29     }
30 }
31 
32 int FindTire(char str[]){
33     int len=strlen(str);
34     Tire *p=root;
35     for(int i=0;i<len;i++){
36         int id=str[i]-'0';
37         if(p->next[id]==NULL||p->next[id]->v==1)
38             return 0;
39         p=p->next[id];
40     }
41     return 1;
42 }
43 //动态开辟空间要释放，不然就要MLE;
44 void DelTire(Tire *root){
45     if(root==NULL)return ;
46     for(int i=0;i<N;i++){
47         if(root->next[i]!=NULL){
48             DelTire(root->next[i]);
49         }
50     }
51     free(root);
52 }
53 
54 int main(){
55     int n,_case;
56     scanf("%d",&_case);
57     while(_case--){
58         scanf("%d",&n);
59         char str[10010][11];
60         root=(Tire *)malloc(sizeof(Tire));
61         for(int i=0;i<N;i++){
62             root->next[i]=NULL;
63         }
64         for(int i=0;i<n;i++){
65             scanf("%s",str[i]);
66             CreateTire(str[i]);
67         }
68         int flag=0;
69         for(int i=0;i<n;i++){
70              flag=FindTire(str[i]);
71             if(flag){
72                 printf("NO\n");
73                 break;
74             }
75         }
76         if(!flag)printf("YES\n");
77         DelTire(root);
78     }
79     return 0;
80 }

附上一大牛的blog:http://www.wutianqi.com/?p=1359