hdu 1075(字典树）

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

wa了好多次啊。。。心都碎了。。。然后不知道怎么一改就对了。。。orz...

建树的的时候每个单词的的最后一个结点应该加入译文的信息。。。

islower()用于判断小写字母很好用。。。

View Code

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 using namespace std;
 5 struct Tire{
 6     char s[14];
 7     Tire *next[26];
 8 };
 9 Tire *root;
10 
11 void CreateTire(char str[],char ss[]){
12     int len=strlen(ss);
13     Tire *p=root,*q;
14     for(int i=0;i<len;i++){
15         int id=ss[i]-'a';
16         if(p->next[id]==NULL){
17             q=(Tire *)malloc(sizeof(Tire));
18             for(int i=0;i<26;i++){
19                 q->next[i]=NULL;
20             }
21             strcpy(q->s,"");
22             p->next[id]=q;
23             p=p->next[id];
24         }else {
25             p=p->next[id];
26         }
27     }
28     strcpy(p->s,str);
29 }
30 
31 Tire *FindTire(string &ss){
32     Tire *p=root;
33     for(int i=0;i<ss.size();i++){
34         int id=ss[i]-'a';
35         if(p->next[id]==NULL)return NULL;
36         p=p->next[id];
37     }
38     if(strcmp(p->s,""))return p;
39     return NULL;
40 }
41 
42 
43 int main(){
44     char str[3300];
45     root=(Tire *)malloc(sizeof(Tire));
46     for(int i=0;i<26;i++){
47         root->next[i]=NULL;
48     }
49     strcpy(root->s,"");
50     while(~scanf("%s",str)){
51         if(str[0]=='S')continue;
52         if(str[0]=='E')break;
53         char ss[14];
54         scanf("%s",ss);
55         CreateTire(str,ss);
56     }
57     getchar();
58     while(gets(str)){
59         if(str[0]=='S')continue;
60         if(str[0]=='E')break;
61         int len=strlen(str);
62         string s;
63         for(int i=0;i<len;i++){
64             s="";
65             if(islower(str[i])){
66                 int k=i;
67                 while(k<len&&islower(str[k])){
68                     s+=str[k];
69                     k++;
70                 }
71                 Tire *p=FindTire(s);
72                 if(p!=NULL){
73                     printf("%s",p->s);
74                 }else {
75                     for(int j=i;j<k;j++){
76                         printf("%c",str[j]);
77                     }
78                 }
79                 i=k-1;
80             }else 
81                 printf("%c",str[i]);
82         }
83         printf("\n");
84     }
85     return 0;
86 }